Watch 10 video solutions for Divide Intervals Into Minimum Number of Groups, a medium level problem involving Array, Two Pointers, Greedy. This walkthrough by NeetCodeIO has 12,553 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 <= 106Problem 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 | 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 |