Divide Intervals Into Minimum Number of Groups — Solution
Divide Intervals Into Minimum Number of Groups solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Divide Intervals Into Minimum Number of Groups is a medium coding problem on arrays, sorting and greedy, asked in Amazon and Google interviews.
- Difficulty: Medium
- Topics: Arrays, Sorting, Greedy, Heap
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given intervals[i] = [left, right], each covering the integers from left to right inclusive.
Split the intervals into groups so that every interval is in exactly one group and no two intervals in the same group intersect — two intervals intersect when they share at least one number, so [1,5] and [5,8] intersect.
Return the minimum number of groups needed.
Example 1
Input: intervals = [[1,4],[4,7],[8,9]]
Output: 2
Explanation: [1,4] and [4,7] share 4, so they need different groups; [8,9] fits with either.
Example 2
Input: intervals = [[5,10],[6,8],[1,5],[2,3],[1,10]]
Output: 3
Example 3
Input: intervals = [[1,3],[5,6],[8,10],[11,13]]
Output: 1
Constraints
1 <= intervals.length <= 10^5intervals[i].length == 21 <= left <= right <= 10^6
Hints for Divide Intervals Into Minimum Number of Groups
Hint 1
If some number lies in
kintervals, thosekintervals needkdifferent groups — so the answer is at least the maximum overlap.Hint 2
Assign intervals in order of
left: reuse a group whose last interval ended strictly before thisleft, otherwise open a new group.Hint 3
That is the same as sweeping sorted
leftvalues against sortedrightvalues: a start reuses a group when the earliest unused end is< left.
How to solve Divide Intervals Into Minimum Number of Groups
The answer is the largest number of intervals that cover one common point. A sweep over sorted starts and sorted ends counts it directly; equivalently, a min-heap of group end times reuses the group that frees up earliest.
Approach
- Sort all
leftvalues and, separately, allrightvalues. - Walk the sorted starts with a pointer
jinto the sorted ends andgroups = 0. - For each start
s: ifends[j] < s, some group has finished — reuse it by advancingj; otherwise open a new group (groups += 1). - Return
groups.
Why it works
Intervals that pairwise share a point need distinct groups, giving the lower bound. The sweep achieves it: a new group is opened only when every group's interval still covers s — that is, when groups intervals plus this one all contain s — so groups never exceeds the maximum overlap. Comparing with < (not <=) encodes inclusivity: an interval ending at s still collides with one starting at s.
Complexity
- Time —
O(n log n) - Space —
O(n)
Pitfalls
- The intervals are closed:
[1,4]and[4,7]intersect, so the test isend < start, notend <= start. - Sorting the starts and the ends independently is valid here because only counts matter, not which interval goes where.
- A difference array over
[1, 10^6 + 1]also works but allocates a large array per call.
Reference solution
Python
from typing import List
def minGroups(intervals: List[List[int]]) -> int:
starts = sorted(iv[0] for iv in intervals)
ends = sorted(iv[1] for iv in intervals)
groups = j = 0
for s in starts:
if ends[j] < s:
j += 1 # a group has finished: reuse it
else:
groups += 1
return groupsJava
public static 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 groups = 0, j = 0;
for (int s : starts) {
if (ends[j] < s) j++; // a group has finished: reuse it
else groups++;
}
return groups;
}C++
int minGroups(vector<vector<int>>& intervals) {
vector<int> starts, ends;
for (auto& iv : intervals) {
starts.push_back(iv[0]);
ends.push_back(iv[1]);
}
sort(starts.begin(), starts.end());
sort(ends.begin(), ends.end());
int groups = 0, j = 0;
for (int s : starts) {
if (ends[j] < s) j++; // a group has finished: reuse it
else groups++;
}
return groups;
}JavaScript
var minGroups = function(intervals) {
var starts = [], ends = [];
for (var i = 0; i < intervals.length; i++) {
starts.push(intervals[i][0]);
ends.push(intervals[i][1]);
}
starts.sort(function(a, b) { return a - b; });
ends.sort(function(a, b) { return a - b; });
var groups = 0, j = 0;
for (var t = 0; t < starts.length; t++) {
if (ends[j] < starts[t]) j++; // a group has finished: reuse it
else groups++;
}
return groups;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Sorting Algorithms