LeetCode 2406 - Divide Intervals Into Minimum Number of Groups

LeetCode Problem 2406

Difficulty: 🟡 Medium
Topics: Array, Two Pointers, Greedy, Sorting, Heap (Priority Queue), Prefix Sum

Solution

Problem Understanding

The problem gives us a list of inclusive intervals, where each interval is represented as [left, right]. We must divide all intervals into groups such that no two intervals inside the same group intersect.

The important detail is that the intervals are inclusive. This means two intervals overlap even if they only share one endpoint. For example, [1, 5] and [5, 8] intersect because both contain the value 5.

We want to determine the minimum number of groups required so that every interval belongs to exactly one group and no group contains overlapping intervals.

Another way to think about the problem is this:

• Each group behaves like a schedule where intervals cannot overlap.
• If several intervals overlap at the same time, they must belong to different groups.
• Therefore, the answer is equal to the maximum number of intervals active simultaneously at any point.

The constraints are important:

• There can be up to 10^5 intervals.
• Interval endpoints can be as large as 10^6.

Because the input size is large, any quadratic solution such as comparing every interval with every other interval will be too slow. We need a solution around O(n log n).

There are several important edge cases to keep in mind:

• Intervals that touch at endpoints still overlap because the intervals are inclusive.
• Multiple identical intervals all overlap with each other.
• A completely non-overlapping set of intervals should return 1.
• Nested intervals such as [1,10], [2,9], [3,8] require multiple groups.
• Large input sizes require an efficient sorting-based or sweep-line-based approach.

Approaches

Brute Force Approach

A straightforward idea is to process intervals one by one and attempt to place each interval into an existing group.

For every interval:

1. Check every existing group.
2. Determine whether the interval overlaps with any interval already in that group.
3. If it does not overlap, place it there.
4. Otherwise, create a new group.

To verify whether an interval fits in a group, we may need to compare it against many intervals already inside the group.

This approach works because it explicitly constructs valid groups while ensuring no overlaps occur within a group. However, it is inefficient because every insertion may require scanning many groups and many intervals inside those groups.

In the worst case, this becomes O(n^2).

With 10^5 intervals, this is far too slow.

Optimal Approach

The key observation is that the minimum number of groups equals the maximum number of overlapping intervals at any moment.

This transforms the problem into an overlap counting problem.

We can solve it efficiently using sorting and a min-heap:

1. Sort intervals by starting position.
2. Use a min-heap to track the ending times of currently active groups.
3. For each interval:

• If the smallest ending time is strictly less than the current start, that group becomes available.
• Otherwise, we need a new group.

4. Push the current interval's end into the heap.

The heap size at any moment represents how many groups are currently in use.

The maximum heap size during processing is the minimum number of groups required.

The crucial detail is the inclusive overlap rule:

• Two intervals overlap if end >= start.
• Therefore, a group can only be reused if previous_end < current_start.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(n)	Explicitly tries placing intervals into groups
Optimal	O(n log n)	O(n)	Uses sorting and a min-heap to track active groups

Algorithm Walkthrough

1. Sort all intervals by their starting point.

Sorting ensures we process intervals from left to right in chronological order. This makes it possible to efficiently determine whether an existing group can be reused. 2. Create a min-heap to store interval ending times.

The heap keeps track of the end value for each active group. The smallest end time is always at the top, which helps us quickly identify the group that becomes available first. 3. Iterate through the sorted intervals.

For each interval [start, end], we check whether the earliest-ending active group can accept this interval. 4. Check the smallest end value in the heap.

If the smallest end value is strictly less than start, then the intervals do not overlap because intervals are inclusive.

Example:

• [1, 3] and [4, 5] do not overlap because 3 < 4
• [1, 3] and [3, 5] do overlap because both include 3

5. Reuse a group if possible.

If heap[0] < start, pop that ending time from the heap because that group is now available. 6. Insert the current interval's end into the heap.

This marks the group as occupied until end. 7. Continue until all intervals are processed.

The heap size represents the number of active groups currently needed. 8. Return the maximum heap size observed.

In this implementation, the heap size after processing all intervals already equals the maximum required because groups are only removed when reusable.

Why it works

The algorithm always reuses the group that becomes available earliest. This greedy strategy is optimal because it preserves as much room as possible for future intervals.

The heap maintains the invariant that it contains the ending times of all currently active groups. Whenever an interval cannot fit into any existing group, a new group must be created. Therefore, the maximum number of simultaneously active intervals equals the minimum number of groups required.

Python Solution

from typing import List
import heapq

class Solution:
    def minGroups(self, intervals: List[List[int]]) -> int:
        intervals.sort()

        min_heap = []

        for start, end in intervals:
            if min_heap and min_heap[0] < start:
                heapq.heappop(min_heap)

            heapq.heappush(min_heap, end)

        return len(min_heap)

The implementation begins by sorting the intervals according to their starting values. Python's default list sorting works correctly because intervals are stored as [start, end].

A min-heap is then used to track active group ending times. The smallest ending time is always accessible in O(1) time through min_heap[0].

For each interval:

• If the earliest-ending group finishes before the current interval starts, that group can be reused.
• We remove that group's ending time from the heap.
• Then we push the current interval's ending time into the heap.

At the end, the heap contains one entry for each active group, and its size equals the minimum number of groups required.

The use of < start instead of <= start is extremely important because intervals are inclusive.

Go Solution

package main

import (
	"container/heap"
	"sort"
)

type MinHeap []int

func (h MinHeap) Len() int {
	return len(h)
}

func (h MinHeap) Less(i, j int) bool {
	return h[i] < h[j]
}

func (h MinHeap) Swap(i, j int) {
	h[i], h[j] = h[j], h[i]
}

func (h *MinHeap) Push(x interface{}) {
	*h = append(*h, x.(int))
}

func (h *MinHeap) Pop() interface{} {
	old := *h
	n := len(old)
	val := old[n-1]
	*h = old[:n-1]
	return val
}

func minGroups(intervals [][]int) int {
	sort.Slice(intervals, func(i, j int) bool {
		if intervals[i][0] == intervals[j][0] {
			return intervals[i][1] < intervals[j][1]
		}
		return intervals[i][0] < intervals[j][0]
	})

	minHeap := &MinHeap{}
	heap.Init(minHeap)

	for _, interval := range intervals {
		start := interval[0]
		end := interval[1]

		if minHeap.Len() > 0 && (*minHeap)[0] < start {
			heap.Pop(minHeap)
		}

		heap.Push(minHeap, end)
	}

	return minHeap.Len()
}

The Go solution follows the same algorithm as the Python version but requires explicit heap implementation because Go's standard library heap utilities operate through interfaces.

The custom MinHeap type implements the heap.Interface.

The sorting step uses sort.Slice, which allows custom comparison logic.

Go slices are dynamic, so the heap naturally grows as intervals are processed.

There are no integer overflow concerns because interval values are bounded by 10^6, well within Go's int range.

Worked Examples

Example 1

Input:

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

Step 1: Sort Intervals

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

Step 2: Process Intervals

Current Interval	Heap Before	Action	Heap After
[1,5]	[]	Add new group	[5]
[1,10]	[5]	5 < 1 is false, new group needed	[5,10]
[2,3]	[5,10]	5 < 2 is false, new group needed	[3,10,5]
[5,10]	[3,10,5]	3 < 5 is true, reuse group	[5,10,10]
[6,8]	[5,10,10]	5 < 6 is true, reuse group	[8,10,10]

Final heap size:

3

Answer:

3

Example 2

Input:

[[1,3],[5,6],[8,10],[11,13]]

Step 1: Sort Intervals

Already sorted.

Step 2: Process Intervals

Current Interval	Heap Before	Action	Heap After
[1,3]	[]	Add group	[3]
[5,6]	[3]	3 < 5, reuse group	[6]
[8,10]	[6]	6 < 8, reuse group	[10]
[11,13]	[10]	10 < 11, reuse group	[13]

Final heap size:

1

Answer:

1

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n log n)	Sorting dominates, heap operations are logarithmic
Space	O(n)	Heap may contain all intervals in worst case

Sorting the intervals requires O(n log n) time. Each interval is inserted into the heap once and possibly removed once. Heap operations take O(log n) time, so the total heap cost is also O(n log n).

The heap can grow to size n in the worst case where all intervals overlap.

Test Cases

from typing import List
import heapq

class Solution:
    def minGroups(self, intervals: List[List[int]]) -> int:
        intervals.sort()

        min_heap = []

        for start, end in intervals:
            if min_heap and min_heap[0] < start:
                heapq.heappop(min_heap)

            heapq.heappush(min_heap, end)

        return len(min_heap)

sol = Solution()

assert sol.minGroups([[5,10],[6,8],[1,5],[2,3],[1,10]]) == 3
# Example with multiple overlaps

assert sol.minGroups([[1,3],[5,6],[8,10],[11,13]]) == 1
# No overlaps at all

assert sol.minGroups([[1,5],[5,10]]) == 2
# Inclusive endpoints overlap

assert sol.minGroups([[1,10],[2,9],[3,8],[4,7]]) == 4
# Fully nested intervals

assert sol.minGroups([[1,1]]) == 1
# Single interval

assert sol.minGroups([[1,2],[3,4],[5,6]]) == 1
# Sequential non-overlapping intervals

assert sol.minGroups([[1,100],[1,100],[1,100]]) == 3
# Identical intervals all overlap

assert sol.minGroups([[1,2],[2,3],[3,4]]) == 2
# Endpoint overlaps force extra groups

assert sol.minGroups([[1,10],[11,20],[21,30]]) == 1
# Clearly separated intervals

assert sol.minGroups([[1,4],[2,5],[7,9],[8,10]]) == 2
# Two independent overlapping regions

assert sol.minGroups([[1,1000000],[2,999999],[3,999998]]) == 3
# Large interval values

Test Case Summary

Test	Why
[[5,10],[6,8],[1,5],[2,3],[1,10]]	Validates complex overlapping scenario
[[1,3],[5,6],[8,10],[11,13]]	Validates no-overlap case
[[1,5],[5,10]]	Ensures inclusive endpoints are handled correctly
[[1,10],[2,9],[3,8],[4,7]]	Tests deeply nested overlaps
[[1,1]]	Smallest valid input
[[1,2],[3,4],[5,6]]	Repeated reuse of a single group
[[1,100],[1,100],[1,100]]	All intervals overlap completely
[[1,2],[2,3],[3,4]]	Mixed endpoint overlap behavior
[[1,10],[11,20],[21,30]]	Completely separated intervals
[[1,4],[2,5],[7,9],[8,10]]	Multiple independent overlap clusters
[[1,1000000],[2,999999],[3,999998]]	Large endpoint values

Edge Cases

One important edge case involves intervals that touch at endpoints. Because the intervals are inclusive, [1,5] and [5,10] overlap. A common bug is using <= instead of < when checking whether a group can be reused. This implementation correctly uses heap[0] < start, ensuring endpoint-sharing intervals remain in separate groups.

Another critical edge case is when all intervals overlap completely. For example, [[1,10],[1,10],[1,10]] requires three groups. The heap grows to size three because no interval can reuse an existing group. This verifies that the algorithm properly tracks simultaneous overlaps.

A third important case is when intervals never overlap. Inputs like [[1,2],[3,4],[5,6]] should only require one group. The algorithm repeatedly removes the smallest ending time from the heap and reuses the same group efficiently.

Nested intervals are also significant. In cases such as [[1,10],[2,9],[3,8]], every interval overlaps with all others. The algorithm correctly identifies that each interval requires its own group because no heap entry satisfies the reuse condition.

Finally, the implementation handles very large inputs efficiently. Since the solution only performs sorting and logarithmic heap operations, it scales comfortably to the maximum constraint of 10^5 intervals.