Sponsored
Sponsored
This approach involves sorting intervals by starting times and then greedily finding the minimum number of groups. When an interval starts after the end of another interval, they can be in the same group; otherwise, they need different groups.
The key insight is to manage the end times of groups using a priority queue (or a min-heap).
Time Complexity: O(n log n), due to sorting.
Space Complexity: O(n), for storing end times.
1#include <stdio.h>
2#include <stdlib.h>
3
4int compare(const void *a, const void *b) {
5 return ((int *)a)[0] - ((int *)b)[0];
6}
7
8int minGroups(int** intervals, int intervalsSize, int* intervalsColSize) {
9 if (intervalsSize == 0) return 0;
10 qsort(intervals, intervalsSize, sizeof(int*), compare);
11 int endTimes[intervalsSize];
12 int groupCount = 0;
13 for (int i = 0; i < intervalsSize; ++i) {
14 int start = intervals[i][0], end = intervals[i][1];
15 int placed = 0;
16 for (int j = 0; j < groupCount; ++j) {
17 if (endTimes[j] < start) {
18 endTimes[j] = end;
19 placed = 1;
20 break;
21 }
22 }
23 if (!placed) {
24 endTimes[groupCount++] = end;
25 }
26 }
27 return groupCount;
28}
29The implementation sorts intervals based on the start time, uses the endTimes array to track end times of intervals in each group, and iteratively places each interval in the earliest non-overlapping group. If no such group is available, a new one is created.
This approach uses a sweep line algorithm where events are created for interval starts and ends. By tracking a count of ongoing intervals, the maximum number of overlapping intervals at any point can be determined, which corresponds to the minimum number of groups required.
It effectively converts the problem into finding the peak number of overlapping intervals.
Time Complexity: O(n log n) for sorting events.
Space Complexity: O(n), events list.
The JavaScript solution builds an events array for start and end points, processes these sorted events similarly, and captures the maximum overlap count as the group's objective.