2406.divide-intervals-into-minimum-number-of-groups.md

2406. Divide Intervals Into Minimum Number of Groups

Line Sweep

We need to divide the intervals into the minimum groups such that no two intervals in the same group overlap. Overlapped intervals won't be in the same group. Idea!! The minimum number of groups means that to find the maximum number of overlapping intervals at any given time. We can use line sweep algorithm to find the maximum overlapping intervals.

• 怎么证明或理解最少的组和最大重合区间数是等价的? 这个是会议室模型，只要任意时刻至多有 x 个会议室在同时使用，那么就至多需要 x 个会议室。
• Good metephor: You calculate how many train platform needed. The train has different arrival and departure time. For the new trains, you have checck whether is there any train which leaves before I come (this is the main reason for keeping min heap). For this we check the top of heap < this trains arrival time, if yes then no need for new platform, else we will need a new one.

fun minGroups(intervals: Array<IntArray>): Int {
    val min = intervals.first()[0]
    val max = intervals.maxOf { it[1] }
    val diff = IntArray(max - min + 2) // min .. max + 1
    for ((left, right) in intervals) {
        diff[left - min]++
        diff[right - min + 1]--
    }
    var value = 0
    var maxOverlap = 0
    for (i in diff.indices) {
        value += diff[i]
        maxOverlap = maxOf(maxOverlap, value)
    }
    return maxOverlap
}

Time complexity: O(n + range), where n is the length of the array intervals, where range is the range of the intervals. Space complexity: O(range).

Or equivalently, we can use TreeMap to store the changes of the intervals.

fun minGroups(intervals: Array<IntArray>): Int {
    val diff = TreeMap<Int, Int>()
    for ((left, right) in intervals) {
        diff[left] = (diff[left] ?: 0) + 1
        diff[right + 1] = (diff[right + 1] ?: 0) - 1
    }
    var value = 0
    var maxOverlap = 0
    for (v in diff.values) {
        value += v
        maxOverlap = maxOf(maxOverlap, value)
    }
    return maxOverlap
}

Time complexity: O(n log n), where n is the length of the array intervals. Space complexity: O(n).

Heap

• 答案或者輸入到順序無關 → 先想到排序，排序後可以給我們一個很好的性質，排序後我們就可以從最小的左區間開始排。我們先照左區間排序。
• 我們分組討論可能的狀況：
  • Case 1. 如果現在沒有群組：肯定要加新的組

  |---*---|

  • Case 2. 如果現在只有一個組：要嘛加在那個組，要不建立新的組。那要怎麼判斷能否能否加入一個組呢？如果新的區間左端點小於組裡面最右邊區間的右端點，那麼也要加到一個新的組，否則是可以加到那個組。

  |------| |---*---|
  
  // Or
  |------|
      |---*---|

  • Case 3. 如果現在有多個群組：一樣要看新區間的左端點是否能接在哪一個組上。簡化邏輯：放在最快結束的區間那個組的後面即可。

  // 新區間的左端點小於組的右端點
  |------| |--*--|
      |------|
  
  // Or 新區間都大於所有的組：這時候放哪個組對於後續是沒有影響的
  |------|      |--new 1--|
      |------|  |--new 1--|

• 需要一個資料結構讓我們決定目前新的區間要放在哪一個群組內。我們需要快速找到每個組裡面右端點最小的那個組？同時還要更新一下該組的右端點？ → Min heap 最小堆代表目前總共需要幾組 (至少需要多少會議室)，堆追蹤每個組的右端點，堆頂代表目前最小的右端點。

Idea!! We use a min heap to track the rightmost number of each group. We can reuse the group if there is no overlapping, otherwise we need to create a new group.

The maximum chance of not getting an overlap is with the with that interval which has smallest end value. If it can't add current group in the smallest end value interval, then it won't merge with any of the other processed intervals.

             // new interval to add
             |-------|

// Current heap: (groups)
-----| // <-- the earliest rightmost of the group, the maximum chance of not getting an overlap
-------|
---------------|

1. Sort the intevals by the start time. This ensures that we can always process the earliest ones first.
2. To track the current groups' earliest end time:
   • The heap stores the right time of each groups.
   • The heap size at any time represents the number of concurrent overlapping intervals, which is the minimum number of groups we need.
3. Check if we can reuse the group (Greedy):
   • No overlapping: heap.peek() < left, we can reuse the group and add that interval to that group. We pop and push right to update the rightmost of that group. For example [1, 5] < [6, 8], we pop [1, 5] and add [6, 8] to the heap, [6, 8] will be the latest earliest right time of that group.
   • Overlapping: we must create a new group by adding the right time to the heap.

// 将数组按照左边界排序，堆顶存放右边界
// |________|            堆为空，入堆(size = 0 -> size = 1)
//     |________|        当前区间和堆顶有重合，入堆(size = 1 -> size = 2)
//            |________| 当前区间和堆顶无重合，堆顶弹出，压入新的右边界(size = 2 -> size = 1 -> size = 2)

Why don't we need to check other groups if there is an overlap?

• heap.peek() < left: No overlap, reuse the group.
• heap.peek() ≥ left: Overlap, no need to check other groups as well, because min heap = [3, 3, 5, 10] > left = 2, it's impossible to find all values in heap < left = 2, all intervals in heap are overlapping as well.

fun minGroups(intervals: Array<IntArray>): Int {
    intervals.sortBy { it[0] }

    val minHeap = PriorityQueue<Int>()
    for ((left, right) in intervals) {
        // No overlap, reuse the group.
        if (minHeap.isNotEmpty() && minHeap.peek() < left) {
            minHeap.poll()
            minHeap.add(right) // Update the `end` of the reused group.
        } else {
            minHeap.add(right) // Create a new group.
        }
    }
    return minHeap.size
}

Time complexity: O(n log n), where n is the length of the array intervals. Space complexity: O(n).

Why not sort by right time?

The heap invariant is

"At the moment you process a meeting, the heap contains only meetings that have already started (i.e., whose starts are ≤ the current meeting’s start). Therefore, checking heap.peek() <= current.start correctly tells you whether a room has freed up."

If you don’t process meetings in non‑decreasing start time, that invariant breaks. Then you might treat a non-overlap as an overlap and allocate an extra room by mistake.

For example, [10, 20], [0, 5] not sorted by start time:

Process in this (bad) order:

• [10,20] → heap = [20] (1 room)
• [0,5] → heap.peek() = 20 is not <= 0, so you allocate another room → heap = [5, 20] (2 rooms) which is wrong.

Process in start time order (correct):

• [0,5] → heap = [5] (1 room)
• [10,20] → heap.peek() = 5 is <= 10, so you can reuse the room → heap = [5, 20] (1 room)

Dry Run

// After sorting the intervals by the left time
[1,5], [1,10], [2,3], [5,10], [6,8]

// Iterate the intervals
[1,5] , heap is empty           , heap.add(5)   [5]
[1,10], heap.peek() = 5 < 1? no , heap.add(10)  [5,10]
[2,3] , heap.peek() = 5 < 2? no , heap.add(3)   [3,5,10]

// At this moment, there are 3 groups, `[1,5], [1,10], [2,3]` because they are overlapping

// Now we can reuse the group from [2,3], so we update that group by replacing `[2,3]` with `[5,10]`
[5,10], heap.peek() = 3 < 5? yes, heap.poll() = 3, heap.add(10)  [5,10,10]

// Same as above, we can reuse the group from [1,5], so we update that group by replacing `[1,5]` with `[6,8]`
[6,8] , heap.peek() = 5 < 6? yes, heap.poll() = 5, heap.add(8)   [8,10,10]