Non-overlapping Intervals

LeetCode 435 題意

• 給定一組區間，移除最少數量的區間，使得剩下的區間互不重疊。
• 回傳需要移除的區間數量。
• Ex.
  Input: [[1,2],[2,3],[3,4],[1,3]]
  Output: 1 (移除 [1,3])

thoughts

• Greedy
• 按照區間結束點排序。
• 遍歷區間，維護一個 end：
  • 若當前區間起點 < end → 需要刪除（計數 +1）。
  • 否則更新 end = 當前區間結束點。
• 時間：O(n log n)
• 空間：O(1)

Kotlin

fun eraseOverlapIntervals(intervals: Array<IntArray>): Int {
    if (intervals.isEmpty()) return 0
    intervals.sortBy { it[1] }

    var count = 0
    var end = intervals[0][1]

    for (i in 1 until intervals.size) {
        if (intervals[i][0] < end) {
            count++  // 重疊，刪除當前
        } else {
            end = intervals[i][1]
        }
    }
    return count
}

Follow-up

• 如果區間是動態新增的，如何即時計算？
• 如果允許部分重疊（例如允許最多 k 個重疊），如何改？
• 如何應用在行程排程 / CPU 時間片分配？