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.
1from heapq import heappop, heappush
2
3def minGroups(intervals):
4 intervals.sort()
5 min_heap = []
6 for start, end in intervals:
7 if min_heap and min_heap[0] < start:
8 heappop(min_heap)
9 heappush(min_heap, end)
10 return len(min_heap)
11This solution sorts the intervals and employs a min-heap to keep track of the end times of overlapping intervals. It pops the heap's top when the current interval can start a new group and pushes the new end time onto it.
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.
In Python, an events list is constructed similarly with increments and decrements at interval bounds, and the maximum number of overlapping intervals is found after sorting.