[LeetCode] 2406. Divide Intervals Into Minimum Number of Groups, C

Solution

- Use qsort(2D array, 2 column) & Greedy Algorithms

- Time Limit Exceed

 

int minGroups(int** intervals, int intervalsSize, int* intervalsColsize)
{
	int i = 0;
	int** RefArr;
	int RefArrSize = intervalsSize;
	int** TmpArr;
	int TmpArrSize = intervalsSize;
	int NumOfGroup = 0;
	int StartIndex = 0;
	int EndIndex = 0;


	// Sort
	qsort(intervals, intervalsSize, sizeof(intervals[0]), compare2Darray2Column);


	// Grouping - greedy algorithms
	RefArr = malloc(RefArrSize * sizeof(int*));
	for (i = 0; i < RefArrSize; i++)
	{
		RefArr[i] = malloc((*intervalsColsize) * sizeof(int));
		RefArr[i][0] = intervals[i][0];
		RefArr[i][1] = intervals[i][1];
	}


	TmpArr = malloc(TmpArrSize * sizeof(int*));
	for (i = 0; i < TmpArrSize; i++)
	{
		TmpArr[i] = malloc((*intervalsColsize) * sizeof(int));
	}



	while (TmpArrSize != 0)
	{
		if (TmpArrSize != 0)
		{
			++NumOfGroup;
		}
		else
		{
			break;
		}

		StartIndex = RefArr[0][0];
		EndIndex = RefArr[0][1];
	
		TmpArrSize = 0;

		for (i = 1; i != RefArrSize; ++i)
		{
			if (RefArr[i][0] > EndIndex)
			{
				EndIndex = RefArr[i][1];
			}
			else
			{
				TmpArr[TmpArrSize][0] = RefArr[i][0];
				TmpArr[TmpArrSize][1] = RefArr[i][1];
				++TmpArrSize;
			}
		}

		for (i = 0; i != TmpArrSize; ++i)
		{
			RefArr[i][0] = TmpArr[i][0];
			RefArr[i][1] = TmpArr[i][1];
		}
		RefArrSize = TmpArrSize;
	}

	return NumOfGroup;
}