Divide Intervals Into Minimum Number of Groups
Problem
You are given intervals [left, right] with both endpoints inclusive (1 ≤ left ≤ right ≤ 10⁶, up to 10⁵ intervals). Distribute all of them into groups so that no two intervals in the same group intersect — and because the endpoints are inclusive, intervals that merely touch, like [1, 5] and [5, 8], still intersect at the shared point 5.
Return the minimum number of groups needed to hold every interval.
intervals = [[5,10],[6,8],[1,5],[2,3],[1,10]]3import heapq
def min_groups(intervals):
intervals.sort()
heap = [] # min-heap of group end times
for left, right in intervals:
if heap and heap[0] < left:
heapq.heapreplace(heap, right) # reuse that group
else:
heapq.heappush(heap, right) # open a new group
return len(heap)function minGroups(intervals) {
intervals.sort((a, b) => a[0] - b[0]);
const heap = []; // min-heap of group end times
const push = (v) => {
heap.push(v);
for (let i = heap.length - 1; 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) heap[0] = last;
for (let i = 0; ; ) {
let m = i; const l = 2 * i + 1, r = 2 * i + 2;
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 [left, right] of intervals) {
if (heap.length && heap[0] < left) pop(); // reuse that group
push(right); // its end becomes right
}
return heap.length;
}int minGroups(int[][] intervals) {
Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
PriorityQueue<Integer> heap = new PriorityQueue<>(); // group ends
for (int[] iv : intervals) {
if (!heap.isEmpty() && heap.peek() < iv[0])
heap.poll(); // reuse that group
heap.offer(iv[1]); // its end becomes iv[1]
}
return heap.size();
}int minGroups(vector<vector<int>>& intervals) {
sort(intervals.begin(), intervals.end());
priority_queue<int, vector<int>, greater<int>> heap; // group ends
for (auto& iv : intervals) {
if (!heap.empty() && heap.top() < iv[0])
heap.pop(); // reuse that group
heap.push(iv[1]); // its end becomes iv[1]
}
return heap.size();
}Explanation
A group may only hold intervals that are pairwise disjoint, so each group is a chain of intervals laid end to end — exactly like one meeting room hosting back-to-back meetings. The question "how few groups?" is therefore the classic meeting rooms question: the answer equals the peak overlap, the largest number of intervals alive at any single point.
We sweep the intervals in sorted start order and keep a min-heap of group end times, one entry per group. For each interval [left, right] only one group is worth checking: the one that frees up earliest, sitting at the heap top. If heap[0] < left (strict, because inclusive endpoints make touching intervals conflict), that group is finished before this interval begins, so we reuse it — pop the old end and push right. Otherwise even the earliest-ending group still overlaps, so every group does, and we must open a new one by pushing right.
Walking the default example, sorted order is [1,5], [1,10], [2,3], [5,10], [6,8]. The first three all overlap near the points 2–3, so three groups open with ends {3, 5, 10}. Then [5,10] arrives: the smallest end 3 is before 5, so it reuses that group (ends become {5, 10, 10}), and [6,8] reuses the group that ended at 5. The heap never grows past 3, and 3 is the answer.
Why is this optimal? A new group is opened only when the incoming start is not after any stored end. Since starts are processed in increasing order, every existing group's current interval contains that start point — so when the k-th group opens, k intervals share one common point and any valid grouping needs at least k groups. The heap size is simultaneously achievable and a lower bound, hence minimal.
Sorting costs O(n log n) and each interval does one heap push plus at most one pop at O(log n) each, so the total time is O(n log n) with O(n) extra space for the heap.