Divide intervals into minimum number of groups

Array Two Pointers Greedy Sorting Heap (Priority Queue) Prefix Sum

63.6% acceptance

Feb 25, 2026

1460

A half-open interval [left, right) is the collection of all real numbers x such that left <= x < right. You are given a 2D integer array intervals where intervals[i] = [lefti, righti] represents the half-open interval [lefti, righti). You may split intervals into groups. Each interval can be assigned to exactly one group. We say that a group of intervals is good if no two intervals in the group intersect each other. Return the minimum number of groups you need to make all the intervals good.

Solution

Rust

Time O(n log n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn min_groups(intervals: Vec<Vec<i32>>) -> i32 {
    let mut events: Vec<(i32, i32)> = Vec::new();
    for iv in &intervals {
      events.push((iv[0], 1));
      events.push((iv[1] + 1, -1));
    }
    events.sort();
    let mut max_overlap = 0;
    let mut cur = 0;
    for (_, delta) in events {
      cur += delta;
      max_overlap = max_overlap.max(cur);
    }
    max_overlap
  }
}