2406. Divide Intervals Into Minimum Number of Groups

Array Greedy Sorting Heap (Priority Queue)Prefix Sum

Time: O(n log n)

Space: O(n)

Intuition

Minimum number of groups to cover all intervals without overlapping in each group. Greedy: sort by start, use min-heap of group end times.

Algorithm

1Sort intervals. Min-heap of end times. For each interval: if heap.min < interval.start: replace (reuse group). Else: add new group.
2Return heap size.

Common Pitfalls

•Equivalent to finding maximum overlap at any point = minimum groups needed.

2406.cs

// Approach: Sort by start; use min-heap of end times; each overlapping interval needs a new group.
// Time: O(n log n) Space: O(n)

public class Solution
{
    public int MinGroups(int[][] intervals)
    {
        // Stores `right`s.
        PriorityQueue<int, int> minHeap = new PriorityQueue<int, int>();

        Array.Sort(intervals, (a, b) => a[0].CompareTo(b[0]));

        foreach (var interval in intervals)
        {
            // There's no overlap, so we can reuse the same group.
            if (minHeap.Count > 0 && interval[0] > minHeap.Peek())
                minHeap.Dequeue();
            minHeap.Enqueue(interval[1], interval[1]);
        }

        return minHeap.Count;
    }
}

Was this solution helpful?