区间调度

📌 核心概念

区间调度问题是贪心算法的经典应用，核心思想是按结束时间排序，选择最早结束的活动。

贪心策略：每次选择结束时间最早且不冲突的区间，这样能为后续活动留出最多时间。

💻 算法实现

🎯 经典应用

💡 解题技巧

1. 排序策略选择

• 按结束时间排序：最多不重叠区间、射箭问题
• 按开始时间排序：会议室判断、合并区间
• 按区间长度排序：某些特殊情况

3. 扫描线技巧

将区间的开始和结束分开处理，模拟扫描线从左到右扫描：

• 遇到开始点：计数+1
• 遇到结束点：计数-1
• 记录过程中的最大值

📊 复杂度分析

问题	排序依据	时间复杂度	空间复杂度
无重叠区间	结束时间	O(n log n)	O(1)
会议室	开始时间	O(n log n)	O(1)
会议室II	扫描线	O(n log n)	O(n)
射箭问题	结束位置	O(n log n)	O(1)
合并区间	开始位置	O(n log n)	O(n)
划分字母区间	无需排序	O(n)	O(1)

Go 代码

// 无重叠区间
func eraseOverlapIntervals(intervals [][]int) int {
    if len(intervals) == 0 {
        return 0
    }
 
    // 按结束时间排序
    sort.Slice(intervals, func(i, j int) bool {
        return intervals[i][1] < intervals[j][1]
    })
 
    count := 1
    end := intervals[0][1]
 
    for i := 1; i < len(intervals); i++ {
        if intervals[i][0] >= end {
            count++
            end = intervals[i][1]
        }
    }
 
    return len(intervals) - count
}
 
// 会议室II
func minMeetingRooms(intervals [][]int) int {
    if len(intervals) == 0 {
        return 0
    }
 
    starts := make([]int, len(intervals))
    ends := make([]int, len(intervals))
 
    for i, interval := range intervals {
        starts[i] = interval[0]
        ends[i] = interval[1]
    }
 
    sort.Ints(starts)
    sort.Ints(ends)
 
    rooms := 0
    maxRooms := 0
    s, e := 0, 0
 
    for s < len(starts) {
        if starts[s] < ends[e] {
            rooms++
            if rooms > maxRooms {
                maxRooms = rooms
            }
            s++
        } else {
            rooms--
            e++
        }
    }
 
    return maxRooms
}
 
// 合并区间
func merge(intervals [][]int) [][]int {
    if len(intervals) == 0 {
        return [][]int{}
    }
 
    sort.Slice(intervals, func(i, j int) bool {
        return intervals[i][0] < intervals[j][0]
    })
 
    merged := [][]int{intervals[0]}
 
    for i := 1; i < len(intervals); i++ {
        last := merged[len(merged)-1]
        if intervals[i][0] <= last[1] {
            if intervals[i][1] > last[1] {
                last[1] = intervals[i][1]
            }
        } else {
            merged = append(merged, intervals[i])
        }
    }
 
    return merged
}

🎯 经典题目

题目	LeetCode	难度	关键点
无重叠区间	435	中等	按结束时间排序
会议室	252	简单	判断冲突
会议室II	253	中等	扫描线
射箭引爆气球	452	中等	同无重叠区间
合并区间	56	中等	按开始时间排序
插入区间	57	中等	合并变形
划分字母区间	763	中等	记录最后位置
汇总区间	228	简单	连续数字

---

返回：贪心算法