【LeetCode】2406、将区间分为最少组数

文章目录

一、数据结构-堆、贪心
- 1.1 数据结构-堆、贪心
- 1.2 多语言解法
二、扫描线
- 2.1 扫描线

一、数据结构-堆、贪心

1.1 数据结构-堆、贪心

题目已知一些区间, 需要尽量合并, 使组最少.

可以用图解画一下

因为尽量合并, 为了紧凑, 尽量按 left 从小到大依次处理. 而题目答案也和顺序无关(因为只需要组的数目), 所以可以排序.
以示例一为例, 如果已经有 [1, 5] 的情况下, [1, 10] 因为和 [1, 5] 有交集所以必须单独成组. 则分为两个组, 如下
接下来, 再放 [2, 3], 其实 [2, 3] 也和 [1, 5] 重叠 (核心是 [2, 3] 的左端点2, 小于 [1, 5] 的右端点 5), 所以无法和 [1, 5] 合并, 而必须单独成组, 如下:
接下来, 再放 [5, 10], 其实只需要考虑已有各组的最小的右端点(即 [2, 3] 的 3 是最小的), 而 [5, 10] 和 [2, 3] 并不相交, 所以可以合并
接下来, 再放 [6, 8], 此时最小的右端点的组为 [1, 5], 而 [6, 8] 和 [1, 5] 并不相交, 所以可以合并为一个组, 如下:

通过推导, 可总结出

如果新区间可和右端点最小的组合并, 则是最紧凑的, 则应合并尽量合并, 并更新 “右端点最小的组的新右端点” 这是贪心的思想.
否则, 新区间应单独成组.

而如何快速找到 “右端点最小的组”, 且更新 “右端点最小的组的新右端点” 呢? => 堆 => 最小堆维护各组的右端点即可

所以伪代码如下:

按左端点, 排序各区间
准备一个堆(其中放的是各组的 right), 遍历各区间
2.1 若 “新区间的 left” > “right最小的组的 right”, 则意味着可合并二者, 则把堆顶替换为 “新区间的 right” 并 heapify 调整堆
2.2 若 “新区间的 left” <= “right最小的组的 right” 或堆为空, 则需单独成组
最终堆的大小即为组的个数, 即为答案

// go
func minGroups(intervals [][]int) int {
    sort.Slice(intervals, func(i, j int) bool {
        return intervals[i][0] < intervals[j][0] // 按左端点排序
    })
    h := hp{}
    for _, p := range intervals {
        left, right := p[0], p[1]
        if h.Len() > 0 && left > h.IntSlice[0] {
            h.IntSlice[0] = right // 把新区间的right, 放入堆顶
            heap.Fix(&h, 0) // heapify 堆顶 (第0下标的就是堆顶)
        } else {
            heap.Push(&h, right)
        }
    }
    return h.Len()
}

type hp struct {sort.IntSlice}
func (h *hp) Push(v any) {h.IntSlice = append(h.IntSlice, v.(int))}
func (h *hp) Pop() any {a := h.IntSlice; v := a[len(a)-1]; h.IntSlice = a[:len(a)-1]; return v}

灵神视频
灵神题解

1.2 多语言解法

$Cpp / G o / P y t h o n / R u s t / J s / T s$

// cpp

// go 同上

# python
class Solution:
    def minGroups(self, intervals: List[List[int]]) -> int:
        intervals.sort()
        h = []
        for left, right in intervals: # [[l1, r1], [l2, r2], [l3, r3]]
            if h and left > h[0]: # 可合并 新区间[l,r] 和 老组, 其中 h[0] 是堆顶(表示 最小right的组 的right)
                heapreplace(h, right) # 把新区间的right, 作为该组(合并后的组) 的新right
            else: # 无法合并, (有交集, 或堆为空), 则新区间需单独成组
                heappush(h, right)
        return len(h)

// rust

// js

// ts

二、扫描线

2.1 扫描线

题目本质是问, 同一时刻, 最多有几个组 (和253题: 同一时刻最多几个会议室是同样的模板)
可以用差分数组, 记录会议的变化(增加或减少会议)

如上图所示:
1时刻增加二个会议室 (因[1, 5] 增加一个, 因 [1, 10] 增加一个)
2时刻增加一个会议室 (因[2, 3] 增加一个)
3时刻减少一个会议室 (因[2, 3] 减少一个)
5时刻增加一个会议室 (因 [5, 10] 增加一个)
5时刻减少一个会议室 (因 [1, 5] 减少一个)
6时刻增加一个会议室 (因 [6, 8] 增加一个)
8时刻减少一个会议室 (因 [6, 8] 减少一个)

注意边界条件为5时刻, 虽然同时增加且减少一个, 但还是不能相互抵消, 即如下图需要先从2增加到3再减少回2. 毕竟此时刻两个会议室都需要被占用(因为前一个会议室还没有结束嘛)
![]](https://i-blog.csdnimg.cn/direct/b57cde44df3d4566bd769978433e3017.png)
所以为了处理这种边界条件, 可视为 [left, right] 的闭区间为 [left, right+1] 的闭区间, 即视为 right +1 会议才结束

func minGroups(intervals [][]int) (ans int) {
    diff := map[int]int{}
    for _, p := range intervals {
        left, right := p[0], p[1]
        diff[left]++
        diff[right+1]--
    }

    // ds 排序, 从而方便从小到大遍历
    keys := []int{}
    for k := range diff { keys = append(keys, k) } // 收集的是下标
    slices.Sort(keys)

    sum := 0 // 差分数组, 求前缀和, 得到的当前时刻的会议室数目
    for _, k := range keys {
        sum += diff[k] // 通过k找到对应的会议室数目 diff[k]
        ans = max(ans, sum) // d 为会议室的变化, sum 为 会议室的数目, ans 为最多的会议室数目
    }
    return ans
}