Divide Intervals Into Minimum Number of Groups
Divide Intervals Into Minimum Number of Groups is a medium intervals problem solved with the line sweep pattern.
The best approach, optimal (line sweep over sorted starts and ends), runs in O(n log n) time and O(n) space.
Below are 3 approaches in Java, Python, C++ and JavaScript, from brute force (count overlaps at every left end) up.
Problem
You are given a list of closed intervals, where intervals[i] = [left_i, right_i] covers every integer from left_i to right_i, both ends included.
Split the intervals into groups so that every interval belongs to exactly one group and no two intervals in the same group share a point. Return the smallest number of groups needed.
Examples
Example 1
- Input
intervals = [[2, 4], [6, 9], [3, 7], [1, 2], [8, 10]]- Output
2- Why
- Group A = [1, 2], [3, 7], [8, 10] and group B = [2, 4], [6, 9]. One group is not enough because [1, 2] and [2, 4] share the point 2.
Example 2
- Input
intervals = [[1, 3], [4, 6], [7, 9]]- Output
1- Why
- No two intervals share a point, so they all fit in a single group.
Example 3
- Input
intervals = [[5, 5], [1, 10], [5, 8], [2, 5]]- Output
4- Why
- All four intervals contain the point 5, so each needs its own group.
Constraints
1 <= intervals.length <= 10^5intervals[i].length == 21 <= left_i <= right_i <= 10^6
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (3 examples, or your own). Submit also runs 11 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (count overlaps at every left end) | O(n²) | O(1) |
| Sort by start + min-heap of group ends | O(n log n) | O(n) |
| Optimal (line sweep over sorted starts and ends) | O(n log n) | O(n) |
1Brute force (count overlaps at every left end)
O(n²)For each of the n candidate points we scan all n intervals.O(1)Only counters.The answer equals the maximum number of intervals that share a point, and the busiest point can always be taken to be some interval's left end. So for each left end, count how many intervals contain it and keep the maximum.
- best = 0.
- For each interval i, count the intervals j with left_j <= left_i <= right_j.
- best = max(best, count); return best.
class Solution {
public int minGroups(int[][] intervals) {
int best = 0;
for (int[] a : intervals) {
int count = 0;
for (int[] b : intervals)
if (b[0] <= a[0] && a[0] <= b[1]) count++;
best = Math.max(best, count);
}
return best;
}
}class Solution:
def minGroups(self, intervals: List[List[int]]) -> int:
best = 0
for a in intervals:
count = 0
for b in intervals:
if b[0] <= a[0] <= b[1]:
count += 1
best = max(best, count)
return bestclass Solution {
public:
int minGroups(vector<vector<int>>& intervals) {
int best = 0;
for (auto& a : intervals) {
int count = 0;
for (auto& b : intervals)
if (b[0] <= a[0] && a[0] <= b[1]) count++;
best = max(best, count);
}
return best;
}
};function minGroups(intervals) {
let best = 0;
for (const a of intervals) {
let count = 0;
for (const b of intervals)
if (b[0] <= a[0] && a[0] <= b[1]) count++;
best = Math.max(best, count);
}
return best;
}2Sort by start + min-heap of group ends
O(n log n)Sorting plus one push and at most one pop per interval.O(n)The heap can hold one entry per group, up to n.Process intervals by left end. Each group is represented by the right end of its last interval, kept in a min-heap. The group that frees up earliest is on top: if it ended strictly before the current left end, reuse it; otherwise open a new group. The heap size at the end is the number of groups.
- Sort intervals by left end.
- For each interval: if the heap is non-empty and heap.peek() < left, pop it.
- Push right (the group now ends at this interval).
- Return heap size.
class Solution {
public int minGroups(int[][] intervals) {
Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
PriorityQueue<Integer> ends = new PriorityQueue<>();
for (int[] iv : intervals) {
if (!ends.isEmpty() && ends.peek() < iv[0]) ends.poll();
ends.offer(iv[1]);
}
return ends.size();
}
}class Solution:
def minGroups(self, intervals: List[List[int]]) -> int:
intervals.sort(key=lambda a: a[0])
ends = []
for l, r in intervals:
if ends and ends[0] < l:
heapq.heapreplace(ends, r)
else:
heapq.heappush(ends, r)
return len(ends)class Solution {
public:
int minGroups(vector<vector<int>>& intervals) {
sort(intervals.begin(), intervals.end(), [](const vector<int>& a, const vector<int>& b) { return a[0] < b[0]; });
priority_queue<int, vector<int>, greater<int>> ends;
for (auto& iv : intervals) {
if (!ends.empty() && ends.top() < iv[0]) ends.pop();
ends.push(iv[1]);
}
return ends.size();
}
};function minGroups(intervals) {
intervals.sort((a, b) => a[0] - b[0]);
const heap = [];
const push = (v) => {
heap.push(v);
let i = heap.length - 1;
while (i > 0) {
const p = (i - 1) >> 1;
if (heap[p] <= heap[i]) break;
[heap[p], heap[i]] = [heap[i], heap[p]];
i = p;
}
};
const pop = () => {
const top = heap[0], last = heap.pop();
if (heap.length > 0) {
heap[0] = last;
let i = 0;
while (true) {
const l = 2 * i + 1, r = l + 1;
let m = i;
if (l < heap.length && heap[l] < heap[m]) m = l;
if (r < heap.length && heap[r] < heap[m]) m = r;
if (m === i) break;
[heap[m], heap[i]] = [heap[i], heap[m]];
i = m;
}
}
return top;
};
for (const [l, r] of intervals) {
if (heap.length > 0 && heap[0] < l) pop();
push(r);
}
return heap.length;
}3Optimal (line sweep over sorted starts and ends)
O(n log n)Two sorts; the sweep moves each pointer at most n times.O(n)Two arrays of n values.Only the maximum overlap matters, so the intervals do not need to stay paired. Sort all left ends and all right ends separately. Walk the left ends in order; a second pointer skips every right end strictly smaller than the current left end (those intervals are closed). Open intervals = starts seen minus ends passed, and the answer is its maximum.
- starts = sorted lefts, ends = sorted rights, j = 0, best = 0.
- For i in 0..n-1: while ends[j] < starts[i], j++.
- best = max(best, i + 1 - j).
- Return best.
class Solution {
public int minGroups(int[][] intervals) {
int n = intervals.length;
int[] starts = new int[n], ends = new int[n];
for (int i = 0; i < n; i++) {
starts[i] = intervals[i][0];
ends[i] = intervals[i][1];
}
Arrays.sort(starts);
Arrays.sort(ends);
int j = 0, best = 0;
for (int i = 0; i < n; i++) {
while (ends[j] < starts[i]) j++;
best = Math.max(best, i + 1 - j);
}
return best;
}
}class Solution:
def minGroups(self, intervals: List[List[int]]) -> int:
starts = sorted(a[0] for a in intervals)
ends = sorted(a[1] for a in intervals)
j = best = 0
for i, s in enumerate(starts):
while ends[j] < s:
j += 1
best = max(best, i + 1 - j)
return bestclass Solution {
public:
int minGroups(vector<vector<int>>& intervals) {
int n = intervals.size();
vector<int> starts(n), ends(n);
for (int i = 0; i < n; i++) {
starts[i] = intervals[i][0];
ends[i] = intervals[i][1];
}
sort(starts.begin(), starts.end());
sort(ends.begin(), ends.end());
int j = 0, best = 0;
for (int i = 0; i < n; i++) {
while (ends[j] < starts[i]) j++;
best = max(best, i + 1 - j);
}
return best;
}
};function minGroups(intervals) {
const n = intervals.length;
const starts = Int32Array.from(intervals, (a) => a[0]).sort();
const ends = Int32Array.from(intervals, (a) => a[1]).sort();
let j = 0, best = 0;
for (let i = 0; i < n; i++) {
while (ends[j] < starts[i]) j++;
best = Math.max(best, i + 1 - j);
}
return best;
}Edge cases to test
- A single interval: 1 group
- Intervals that only touch at an endpoint, like [1, 2] and [2, 3], still clash (both ends are inclusive)
- Intervals of length zero such as [5, 5]
- All intervals identical: n groups
- Input not sorted
Hints
Hint 1
If k intervals all contain one common point, you need at least k groups. Is that bound always reachable?
Hint 2
It is: the answer is the largest number of intervals covering any single point. That maximum is always reached at some interval's left end.
Hint 3
Sweep the left ends in sorted order and count how many intervals are still open, retiring those whose right end is strictly smaller than the current left end.
FAQ
What is the best time complexity for Divide Intervals Into Minimum Number of Groups?
Optimal (line sweep over sorted starts and ends) runs in O(n log n) time and O(n) extra space. Two sorts; the sweep moves each pointer at most n times.
Which pattern does Divide Intervals Into Minimum Number of Groups use?
It is a intervals problem that uses the line sweep pattern. Other problems with the same pattern: Meeting Rooms II, Car Pooling, Employee Free Time.
Is there a brute force solution for Divide Intervals Into Minimum Number of Groups?
Yes. Brute force (count overlaps at every left end) takes O(n²) time and O(1) space. The answer equals the maximum number of intervals that share a point, and the busiest point can always be taken to be some interval's left end.
Which edge cases should I test for Divide Intervals Into Minimum Number of Groups?
A single interval: 1 group; Intervals that only touch at an endpoint, like [1, 2] and [2, 3], still clash (both ends are inclusive); Intervals of length zero such as [5, 5]; All intervals identical: n groups; Input not sorted.