Divide Intervals Into Minimum Number of Groups

Divide Intervals Into Minimum Number of Groups

What is this problem about?

The Divide Intervals Into Minimum Number of Groups coding problem asks you to take a list of intervals [start, end] and partition them into the smallest possible number of groups such that no two intervals in the same group overlap. Two intervals overlap if they share any common point (e.g., [1, 5] and [5, 10] overlap at point 5).

Why is this asked in interviews?

Companies like Microsoft and Meta use this Greedy interview pattern to evaluate scheduling logic. It's essentially the same as finding the "maximum number of concurrent meetings" or the "minimum number of rooms required." It tests your ability to use Sorting and Heaps to manage overlapping time segments efficiently.

Algorithmic pattern used

There are two main approaches:

1. Min-Heap (Greedy):
   • Sort intervals by start time.
   • Use a Min-Heap to store the end times of the current groups.
   • For each interval, if its start time is greater than the smallest end time in the heap, it can reuse that group (update the end time in the heap).
   • Otherwise, start a new group (push the end time into the heap).
   • The heap size is the answer.
2. Difference Array / Sweep Line:
   • Mark start as +1 and end + 1 as -1.
   • Sort all points and find the maximum prefix sum (maximum concurrency).

Example explanation

Intervals: [[5, 10], [6, 8], [1, 5], [2, 3], [1, 10]]

1. Sort: [1, 5], [1, 10], [2, 3], [5, 10], [6, 8].
2. Process:
   • [1, 5]: New group. Heap: [5].
   • [1, 10]: Overlaps (1 <= 5). New group. Heap: [5, 10].
   • [2, 3]: Overlaps. New group. Heap: [3, 5, 10].
   • [5, 10]: Overlaps (5 <= 3 is false, but wait, rule says inclusive). If [2, 3] ends at 3, and [5, 10] starts at 5, they don't overlap. But point 5 is the issue. If the intervals were [1, 4] and [5, 10], they wouldn't overlap. In this problem, the maximum number of overlapping intervals at any point in time equals the minimum number of groups needed.

Common mistakes candidates make

• Inclusive vs Exclusive: Not carefully checking if start == end constitutes an overlap.
• Sorting by End Time: Sorting by end time is for "Maximum Disjoint Sets," while sorting by start time is for "Minimum Groups/Rooms."
• Inefficient Search: Trying to find a group to fit an interval into by scanning all existing groups instead of using a Min-Heap.

Interview preparation tip

Memorize the "Meeting Rooms II" pattern. This problem is identical. The "Sweep Line" approach is often cleaner to code if you aren't comfortable with heap rebalancing.