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 <vector>
2#include <algorithm>
3#include <queue>
4using namespace std;
5
6int minGroups(vector<vector<int>>& intervals) {
7 sort(intervals.begin(), intervals.end());
8 priority_queue<int, vector<int>, greater<int>> pq;
9 for (auto& interval : intervals) {
10 if (!pq.empty() && pq.top() < interval[0]) {
11 pq.pop();
12 }
13 pq.push(interval[1]);
14 }
15 return pq.size();
16}
17Intervals are sorted by their starting values. A min-heap is used to maintain the end time of intervals in each group. For each interval, if it starts after the earliest ending interval, the earliest is removed from the heap (indicating merging into a single group), and the current interval's end time is added.
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 solution creates events for the start and the end (incremented by 1 for exclusive end point) of each interval. It sorts these events and uses a counter to track ongoing intervals, updating the maximum overlap found.