Description
給定一個區間的集合
intervals，求最少需要移除多少個區間才能讓剩下的區間互不重疊。
Example:
Input: intervals = [[1,2],[2,3],[3,4],[1,3]] Output: 1
Intuition#
等價問題：最多能保留多少個互不重疊的區間？用貪心策略每次選結束最早的區間。
- 這是經典的區間排程（Interval Scheduling）問題
- 按 end 排序，貪心地選結束最早的區間，可以留出最多空間給後面的區間
- 答案 = 總數 - 最多保留數
Approaches#
1: Sort by Start + Count Overlaps#
- 概念: 按起點排序，遇到重疊時移除 end 較大的那個（貪心保留 end 較小的）
- 時間複雜度:
O(n log n) - 空間複雜度:
O(1)— 不計排序空間
class Solution {
fun eraseOverlapIntervals(intervals: Array<IntArray>): Int {
intervals.sortBy { it[0] }
var count = 0
var prevEnd = intervals[0][1]
for (i in 1 until intervals.size) {
if (intervals[i][0] < prevEnd) {
count++
prevEnd = minOf(prevEnd, intervals[i][1])
} else {
prevEnd = intervals[i][1]
}
}
return count
}
}⭐2: Sort by End + Greedy Scheduling#
- 概念: 按終點排序，貪心選取不重疊的區間，最大化保留數量
- 時間複雜度:
O(n log n) - 空間複雜度:
O(1)— 不計排序空間
class Solution {
fun eraseOverlapIntervals(intervals: Array<IntArray>): Int {
intervals.sortBy { it[1] }
var kept = 1
var prevEnd = intervals[0][1]
for (i in 1 until intervals.size) {
if (intervals[i][0] >= prevEnd) {
kept++
prevEnd = intervals[i][1]
}
}
return intervals.size - kept
}
}🔑 Takeaways#
- Pattern: 區間排程 (Interval Scheduling) — 按 end 排序的貪心策略是最優的
- 關鍵技巧: 「最少移除」等價於「最多保留」；按結束時間排序能保證貪心的正確性（直覺：越早結束越好）