Divide Intervals Into Minimum Number of Groups

Medium
1442.

Divide Intervals Into Minimum Number of Groups

MediumArrayGreedySortingHeap (Priority Queue)GoogleAmazon

Divide Intervals Into Minimum Number of Groups is a medium coding problem on arrays, sorting and greedy, asked in Amazon and Google interviews.

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^5
  • intervals[i].length == 2
  • 1 <= left <= right <= 10^6
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[][]} intervals
 * @return {number}
 */
var minGroups = function(intervals) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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^5
  • intervals[i].length == 2
  • 1 <= left <= right <= 10^6

Hints for Divide Intervals Into Minimum Number of Groups

  1. Hint 1

    If some number lies in k intervals, those k intervals need k different groups — so the answer is at least the maximum overlap.

  2. Hint 2

    Assign intervals in order of left: reuse a group whose last interval ended strictly before this left, otherwise open a new group.

  3. Hint 3

    That is the same as sweeping sorted left values against sorted right values: 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

  1. Sort all left values and, separately, all right values.
  2. Walk the sorted starts with a pointer j into the sorted ends and groups = 0.
  3. For each start s: if ends[j] < s, some group has finished — reuse it by advancing j; otherwise open a new group (groups += 1).
  4. 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 is end < start, not end <= 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 groups

Java

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