Divide Intervals Into Minimum Number of Groups
MedPrompt
You are given a 2D integer array intervals where intervals[i] = [lefti, righti] represents the inclusive interval [lefti, righti].
You have to divide the intervals into one or more groups such that each interval is in exactly one group, and no two intervals that are in the same group intersect each other.
Return the minimum number of groups you need to make.
Two intervals intersect if there is at least one common number between them. For example, the intervals [1, 5] and [5, 8] intersect.
Example 1:
Input: intervals = [[5,10],[6,8],[1,5],[2,3],[1,10]]
Output: 3
Explanation: We can divide the intervals into the following groups:
- Group 1: [1, 5], [6, 8].
- Group 2: [2, 3], [5, 10].
- Group 3: [1, 10].
It can be proven that it is not possible to divide the intervals into fewer than 3 groups.Example 2:
Input: intervals = [[1,3],[5,6],[8,10],[11,13]]
Output: 1
Explanation: None of the intervals overlap, so we can put all of them in one group.
Constraints:
1 <= intervals.length <= 105intervals[i].length == 21 <= lefti <= righti <= 106
Approaches
2 approaches with complexity analysis and trade-offs.
This approach sorts the intervals by their start times and then uses a min-heap to manage the groups. The core idea is to simulate the process of assigning each interval to a group. The min-heap efficiently keeps track of the end times of the last interval in each group, allowing us to quickly find a group that an incoming interval can be placed into without causing an overlap.
Algorithm
- Sort the
intervalsarray based on their start times. This allows us to process intervals in a chronological order. - Initialize a min-priority queue (
minHeap) to store the end times of the intervals that are currently occupying a group. The size of the heap will represent the number of groups currently in use. - Iterate through each sorted interval
[start, end]:- Look at the top of the
minHeap. If the heap is not empty and the current interval'sstarttime is greater than the smallest end time in the heap (minHeap.peek()), it means we can reuse the group that finishes earliest. We do this by removing the earliest end time from the heap (minHeap.poll()). - Add the current interval's
endtime to the heap. This either places the interval into a newly freed group (the one we just polled from) or, if no group was freed, it effectively allocates a new group, increasing the heap's size.
- Look at the top of the
- After iterating through all intervals, the final size of the
minHeapis the maximum number of concurrent intervals we ever had, which corresponds to the minimum number of groups required.
Walkthrough
The problem of finding the minimum number of groups for non-overlapping intervals is equivalent to finding the maximum number of intervals that overlap at any single point in time. This value is often called the "point of maximum overlap".
By sorting the intervals by their start times, we can process them chronologically. We use a min-heap to store the end times of the intervals currently assigned to groups. The value at the top of the heap represents the group that will become free the soonest.
When we consider a new interval, we check if it can be placed in any existing group. A group is available if its last interval ends before the new one begins. This corresponds to checking if the new interval's start time is greater than the smallest end time in our heap. If it is, we reuse that group by updating its end time. If not, the new interval overlaps with all currently active groups, so we must create a new group for it, which is done by adding its end time to the heap. The size of the heap at any point reflects the number of groups needed for the intervals processed so far, and its maximum size (which is its final size in this algorithm) gives the overall minimum number of groups.
Complexity
Time
O(N log N), where N is the number of intervals. The sorting step takes O(N log N). The loop iterates through N intervals, and each heap operation (add or poll) takes O(log K) time, where K is the size of the heap (K <= N). This results in a total time complexity dominated by sorting.
Space
O(N), where N is the number of intervals. In the worst-case scenario, if all intervals overlap, the min-heap will need to store an end time for each interval.
Trade-offs
Pros
The logic is intuitive as it directly models the process of assigning meetings to conference rooms.
It's a standard and robust technique for this class of interval problems.
Cons
The use of a Priority Queue can have a slightly higher constant factor overhead compared to a simple array-based sweep line approach.
A more optimized approach is the sweep-line algorithm. This method deconstructs the intervals into individual start and end points. By sorting these points, we can process them as a sequence of events. A 'start' event increases the number of active intervals, and an 'end' event decreases it. The maximum number of active intervals at any point during this 'sweep' gives us the minimum number of groups required.
Algorithm
- Create two separate integer arrays,
startsandends, each of sizeN(the number of intervals). - Populate the
startsarray with all the start times (left_i) and theendsarray with all the end times (right_i) from the input intervals. - Sort both the
startsandendsarrays in non-decreasing order. - Initialize two pointers:
startPointer = 0to iterate throughstarts, andendPointer = 0to iterate throughends. - Iterate with
startPointerfrom0toN-1:- For each
starttime being processed, we are essentially adding a new interval that needs a group. - Compare the current
starts[startPointer]withends[endPointer]. Ifstarts[startPointer] > ends[endPointer], it means the interval that ends earliest has finished before the current interval begins. This frees up a group, so we can advanceendPointer. - The number of active groups at any point is
startPointer - endPointer. SincestartPointeralways increments andendPointeronly increments when a group is freed, the differencestartPointer - endPointeris non-decreasing. Its maximum value will be its final value.
- For each
- The minimum number of groups is
N - endPointerafter the loop finishes.
Walkthrough
This approach elegantly calculates the maximum overlap without explicitly tracking group assignments. We create two arrays, one for all start points and one for all end points. Sorting both allows us to process events chronologically.
We use two pointers, one for the sorted starts and one for the sorted ends. We iterate through the starts array. For each new interval starting, we check if any interval has already ended. An interval ends[endPointer] has ended before starts[startPointer] begins if starts[startPointer] > ends[endPointer]. If so, a group has been freed, and we can advance our endPointer. The number of groups required is the total number of intervals that have started minus the number of intervals that have finished. This is tracked by startPointer - endPointer. The maximum value of this difference is the answer. In this specific implementation, the final result is simply N - endPointer.
This works because [a, b] and [b, c] are considered overlapping. Sorting the start and end points and processing them ensures that at any time t, a start event at t is processed before an end event at t, correctly accounting for the maximum overlap.
Complexity
Time
O(N log N), where N is the number of intervals. The complexity is dominated by sorting the two arrays. The subsequent two-pointer scan takes linear O(N) time.
Space
O(N), where N is the number of intervals, to store the separate `starts` and `ends` arrays.
Trade-offs
Pros
Generally more efficient in practice due to lower overhead than heap operations.
The space complexity is straightforward (two arrays of size N).
The implementation is very concise.
Cons
The logic can be less intuitive to grasp at first compared to the direct simulation with a min-heap.
Solutions
Solution
class Solution {public int minGroups(int[][] intervals) { Arrays.sort(intervals, (a, b)->a[0] - b[0]); PriorityQueue<Integer> q = new PriorityQueue<>(); for (var e : intervals) { if (!q.isEmpty() && q.peek() < e[0]) { q.poll(); } q.offer(e[1]); } return q.size(); }}class Solution {public: int minGroups(vector<vector<int>> &intervals) { sort(intervals.begin(), intervals.end()); priority_queue<int, vector<int>, greater<int>> q; for (auto &e : intervals) { if (q.size() && q.top() < e[0]) { q.pop(); } q.push(e[1]); } return q.size(); }};class Solution: def minGroups(self, intervals: List[List[int]]) -> int: h = [] for a, b in sorted(intervals): if h and h[0] < a: heappop(h) heappush(h, b) return len(h)Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.