Divide Intervals Into Minimum Number of Groups solution and explanation
IBM
Google
9 more videos on this problem
Divide Intervals Into Minimum Number of Groups - Leetcode 2406 - PythonNeetCodeIO · 11:44 · 12K views
Divide Intervals Into Minimum Number of Groups | Simple Intuition | Leetcode 2406 | codestorywithMIKcodestorywithMIK · 20:58 · 10K views
2406. Divide Intervals Into Minimum Number of Groups | Leetcode Daily Challenge | DSA | JavaShashCode · 16:27 · 2K views
Divide Intervals Into Minimum Number of Groups | Leetcode 2406Techdose · 14:18 · 2K views
Divide Intervals Into Minimum Number of Groups | Leetcode 2406 | Optimal+Bonus | Explanation+CodingTech With Anubhav · 36:34 · 818 views
2406. Divide Intervals Into Minimum Number of Groups (Leetcode Medium)Programming Live with Larry · 8:13 · 648 views
2406. Divide Intervals Into Minimum Number of Groups | Sorting | LeetCode | MediumLeet's Code · 14:33 · 227 views
LeetCode 2406 | Divide Intervals Into Minimum Number of Groups | MAANG Interview Prep |Pen and PaperPen And Paper · 3:45 · 104 views
Leetcode 2406. Divide Intervals Into Minimum Number of Groups (difference array)LetsCode · 6:34 · 99 views
Divide Intervals Into Minimum Number of Groups | Leetcode 2406 | Priority Queue Java Developer CoderDeveloper Coder · 10:26 · 80 views
The problem
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).
from heapq import heappop, heappush
def minGroups(intervals):
intervals.sort()
min_heap = []
for start, end in intervals:
if min_heap and min_heap[0] < start:
heappop(min_heap)
heappush(min_heap, end)
return len(min_heap)import java.util.*;
public class Solution {
public int minGroups(int[][] intervals) {
Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
PriorityQueue<Integer> pq = new PriorityQueue<>();
for (int[] interval : intervals) {
if (!pq.isEmpty() && pq.peek() < interval[0]) {
pq.poll();
}
pq.offer(interval[1]);
}
return pq.size();
}
}#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
int minGroups(vector<vector<int>>& intervals) {
sort(intervals.begin(), intervals.end());
priority_queue<int, vector<int>, greater<int>> pq;
for (auto& interval : intervals) {
if (!pq.empty() && pq.top() < interval[0]) {
pq.pop();
}
pq.push(interval[1]);
}
return pq.size();
}const minGroups = (intervals) => {
intervals.sort((a, b) => a[0] - b[0]);
const pq = [];
for (let [start, end] of intervals) {
if (pq.length > 0 && pq[0] < start) {
pq.shift();
}
pq.push(end);
pq.sort((a, b) => a - b);
}
return pq.length;
};#include <stdio.h>
#include <stdlib.h>
int compare(const void *a, const void *b) {
return ((int *)a)[0] - ((int *)b)[0];
}
int minGroups(int** intervals, int intervalsSize, int* intervalsColSize) {
if (intervalsSize == 0) return 0;
qsort(intervals, intervalsSize, sizeof(int*), compare);
int endTimes[intervalsSize];
int groupCount = 0;
for (int i = 0; i < intervalsSize; ++i) {
int start = intervals[i][0], end = intervals[i][1];
int placed = 0;
for (int j = 0; j < groupCount; ++j) {
if (endTimes[j] < start) {
endTimes[j] = end;
placed = 1;
break;
}
}
if (!placed) {
endTimes[groupCount++] = end;
}
}
return groupCount;
}using System;
using System.Collections.Generic;
public class Solution {
public int MinGroups(int[][] intervals) {
Array.Sort(intervals, (a, b) => a[0].CompareTo(b[0]));
var pq = new SortedSet<int>();
foreach (var interval in intervals) {
if (pq.Count > 0 && pq.Min < interval[0]) {
pq.Remove(pq.Min);
}
pq.Add(interval[1]);
}
return pq.Count;
}
}This solution sorts the intervals and employs a min-heap to keep track of the end times of overlapping intervals. It pops the heap's top when the current interval can start a new group and pushes the new end time onto it.
Time Complexity: O(n log n) - involves sorting and heap operations for each interval.
Space Complexity: O(n), required by the min-heap.
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.
def minGroups(intervals):
events = []
for start, end in intervals:
events.append((start, 1))
events.append((end + 1, -1))
events.sort()
ongoing, maxOverlap = 0, 0
for _, change in events:
ongoing += change
maxOverlap = max(maxOverlap, ongoing)
return maxOverlapimport java.util.*;
public class Solution {
public int minGroups(int[][] intervals) {
List<int[]> events = new ArrayList<>();
for (int[] interval : intervals) {
events.add(new int[]{interval[0], 1});
events.add(new int[]{interval[1] + 1, -1});
}
Collections.sort(events, (a, b) -> a[0] - b[0]);
int ongoing = 0, maxOverlap = 0;
for (int[] event : events) {
ongoing += event[1];
maxOverlap = Math.max(maxOverlap, ongoing);
}
return maxOverlap;
}
}#include <vector>
#include <algorithm>
using namespace std;
int minGroups(vector<vector<int>>& intervals) {
vector<pair<int, int>> events;
for (auto& interval : intervals) {
events.push_back({interval[0], 1});
events.push_back({interval[1] + 1, -1});
}
sort(events.begin(), events.end());
int ongoing = 0, maxOverlap = 0;
for (auto& event : events) {
ongoing += event.second;
maxOverlap = max(maxOverlap, ongoing);
}
return maxOverlap;
}const minGroups = (intervals) => {
const events = [];
for (const [start, end] of intervals) {
events.push([start, 1]);
events.push([end + 1, -1]);
}
events.sort((a, b) => a[0] - b[0]);
let ongoing = 0, maxOverlap = 0;
for (const [time, change] of events) {
ongoing += change;
maxOverlap = Math.max(maxOverlap, ongoing);
}
return maxOverlap;
};#include <stdio.h>
#include <stdlib.h>
int comp(const void *a, const void *b) {
return (*(int*)a) - (*(int*)b);
}
int minGroups(int** intervals, int intervalsSize, int* intervalsColSize) {
int events[2 * intervalsSize][2], i, ongoing = 0, maxOverlap = 0;
for (i = 0; i < intervalsSize; i++) {
events[2*i][0] = intervals[i][0];
events[2*i][1] = 1;
events[2*i + 1][0] = intervals[i][1] + 1;
events[2*i + 1][1] = -1;
}
qsort(events, 2 * intervalsSize, sizeof(events[0]), comp);
for (i = 0; i < 2 * intervalsSize; i++) {
ongoing += events[i][1];
if (ongoing > maxOverlap) maxOverlap = ongoing;
}
return maxOverlap;
}using System;
using System.Collections.Generic;
using System.Linq;
public class Solution {
public int MinGroups(int[][] intervals) {
List<Tuple<int, int>> events = new List<Tuple<int, int>>();
foreach (var interval in intervals) {
events.Add(Tuple.Create(interval[0], 1));
events.Add(Tuple.Create(interval[1] + 1, -1));
}
events.Sort((a, b) => a.Item1.CompareTo(b.Item1));
int ongoing = 0, maxOverlap = 0;
foreach (var e in events) {
ongoing += e.Item2;
maxOverlap = Math.Max(maxOverlap, ongoing);
}
return maxOverlap;
}
}In Python, an events list is constructed similarly with increments and decrements at interval bounds, and the maximum number of overlapping intervals is found after sorting.
Time Complexity: O(n log n) due to sorting.
Space Complexity: O(n) for event storage.
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.
function minGroups(intervals: number[][]): number {
intervals.sort((a, b) => a[0] - b[0]);
const q = new PriorityQueue({ compare: (a, b) => a - b });
for (const [left, right] of intervals) {
if (!q.isEmpty() && q.front() < left) {
q.dequeue();
}
q.enqueue(right);
}
return q.size();
}func minGroups(intervals [][]int) int {
sort.Slice(intervals, func(i, j int) bool { return intervals[i][0] < intervals[j][0] })
q := hp{}
for _, e := range intervals {
if q.Len() > 0 && q.IntSlice[0] < e[0] {
heap.Pop(&q)
}
heap.Push(&q, e[1])
}
return q.Len()
}
type hp struct{ sort.IntSlice }
func (h *hp) Push(v any) { h.IntSlice = append(h.IntSlice, v.(int)) }
func (h *hp) Pop() any {
a := h.IntSlice
v := a[len(a)-1]
h.IntSlice = a[:len(a)-1]
return v
}Complexity comparison
| Approach | Complexity |
|---|---|
| Approach 1: Greedy Interval Grouping | Time Complexity: O(n log n) - involves sorting and heap operations for each interval. Space Complexity: O(n), required by the min-heap. |
| Approach 2: Sweep Line Algorithm | Time Complexity: O(n log n) due to sorting. Space Complexity: O(n) for event storage. |
| Greedy + Priority Queue (Min Heap) | – |
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 |
Frequently asked questions
Is Divide Intervals Into Minimum Number of Groups easy or hard?
The problem is rated Medium on LeetCode. It becomes straightforward once you recognize it as a maximum-overlapping-intervals problem similar to Meeting Rooms II.
Divide Intervals Into Minimum Number of Groups Python/Java solution
Python solutions typically use heapq after sorting intervals by start time. Java implementations use PriorityQueue for the same purpose. Both follow the same logic: reuse the group with the smallest end time or create a new group when overlaps occur.
How to solve Divide Intervals Into Minimum Number of Groups in O(n)?
An exact O(n) solution is generally not possible because intervals must be processed in sorted order of their endpoints. The closest optimal approach is O(n log n) using sorting combined with a heap or a sweep line event array.
What is the best approach for Divide Intervals Into Minimum Number of Groups?
The most common solution uses a greedy strategy with a min heap. Sort intervals by start time and track the earliest ending group in a priority queue. If the current interval starts after the earliest end, reuse that group; otherwise create a new one. This runs in O(n log n) time and is the standard interview approach.
Is Divide Intervals Into Minimum Number of Groups asked at Google/Amazon/Meta?
Interval overlap and meeting-room style problems frequently appear in interviews at companies like Google, Amazon, and Meta. This problem is a variation of the classic Meeting Rooms II pattern that tests sorting, greedy reasoning, and priority queue usage.
What data structure is used in Divide Intervals Into Minimum Number of Groups?
The greedy solution relies on a min heap (priority queue) to track the earliest finishing interval among active groups. The sweep line alternative uses an ordered map or event list combined with a prefix sum style accumulation.
What is the time complexity of Divide Intervals Into Minimum Number of Groups?
The optimal complexity is O(n log n). Sorting the intervals dominates the runtime, and heap operations during iteration also cost O(log n). Space complexity is O(n) for the heap or event list used to track active intervals.