Divide Intervals Into Minimum Number of Groups - Solution & Explanation
Problem Statement
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
Approach Overview
Problem Overview: You are given several intervals [start, end]. Intervals that overlap cannot belong to the same group. The task is to divide all intervals into the minimum number of groups so that intervals inside each group never overlap.
The key observation: the answer equals the maximum number of overlapping intervals at any point in time. If three intervals overlap at the same moment, at least three groups are required.
Approach 1: Greedy Interval Grouping with Min Heap (O(n log n) time, O(n) space)
This approach uses sorting and a heap (priority queue). First sort intervals by their start time. Maintain a min‑heap that stores the end time of the last interval in each group. While iterating through the sorted intervals, check the smallest end time in the heap. If the current interval starts after that end time, reuse that group by popping from the heap. Otherwise, create a new group. Push the current interval's end into the heap. The heap size at any moment represents the number of active groups, and the maximum size reached is the answer. This greedy strategy works because reusing the group with the earliest finishing interval minimizes conflicts.
Approach 2: Sweep Line Algorithm (O(n log n) time, O(n) space)
The sweep line technique tracks how many intervals are active at each position. For every interval [l, r], add +1 at l and -1 at r + 1. Store these events and process them in sorted order. As you sweep from left to right, maintain a running sum of active intervals. The maximum value of this running sum is the number of overlapping intervals, which equals the minimum groups needed. This solution is closely related to the prefix sum technique and avoids managing individual groups explicitly.
Recommended for interviews: The greedy heap approach is usually expected because it demonstrates understanding of interval scheduling, greedy algorithms, and priority queues. The sweep line method is equally correct and often simpler conceptually when you recognize the problem as counting maximum overlaps. Showing both ideas signals strong mastery of interval problems.
Approach 1: Approach 1: Greedy Interval Grouping
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).
The 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.
Complexity
Time Complexity: O(n log n), due to sorting.
Space Complexity: O(n), for storing end times.
Approach 2: Approach 2: Sweep Line Algorithm
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.
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.
Complexity
Time Complexity: O(n log n) for sorting events.
Space Complexity: O(n), events list.
Approach 3: Greedy + Priority Queue (Min Heap)
First, we sort the intervals by their left endpoints. We use a min heap to maintain the rightmost endpoint of each group (the top of the heap is the minimum of the rightmost endpoints of all groups).
Next, we traverse each interval:
- If the left endpoint of the current interval is greater than the top element of the heap, it means the current interval can be added to the group where the top element of the heap is located. We directly pop the top element of the heap, and then put the right endpoint of the current interval into the heap.
- Otherwise, it means there is currently no group that can accommodate the current interval, so we create a new group and put the right endpoint of the current interval into the heap.
The time complexity is O(n times log n), and the space complexity is O(n). Here, n is the length of the array intervals.
Code
Python
Java
C++
Go
TypeScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Approach 1: Greedy Interval Grouping | Time Complexity: O(n log n), due to sorting. Space Complexity: O(n), for storing end times. |
| Approach 2: Sweep Line Algorithm | Time Complexity: O(n log n) for sorting events. Space Complexity: O(n), events list. |
| Greedy + Priority Queue (Min Heap) | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Greedy Interval Grouping (Min Heap) | O(n log n) | O(n) | General solution for interval grouping problems; ideal when managing active intervals dynamically |
| Sweep Line Algorithm | O(n log n) | O(n) | When the problem reduces to counting maximum overlaps rather than explicitly forming groups |
Video Solution
Divide Intervals Into Minimum Number of Groups - Leetcode 2406 - Python • NeetCodeIO • 12,818 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Divide Intervals Into Minimum Number of Groups easy or hard?
Divide Intervals Into Minimum Number of Groups Python/Java solution
How to solve Divide Intervals Into Minimum Number of Groups in O(n)?
What is the best approach for Divide Intervals Into Minimum Number of Groups?
Is Divide Intervals Into Minimum Number of Groups asked at Google/Amazon/Meta?
What data structure is used in Divide Intervals Into Minimum Number of Groups?
What is the time complexity of Divide Intervals Into Minimum Number of Groups?
Ready to solve this problem?
Practice Divide Intervals Into Minimum Number of Groups with our built-in code editor and test cases.
Practice on FleetCode