區間問題 (Interval Problems)#

很多看似不相干的題目，骨子裡都是同一件事：輸入是一組 [start, end] 區間，要你在它們之間做點什麼。會議室排程、影片片段去重、行程衝突偵測、頻寬佔用統計——只要資料能被描述成「在數線上佔據一段範圍」，就落進了區間問題這個大家族。

問題家族#

區間問題的輸入通常是一個區間陣列，每個區間有起點與終點。要解的事情大致分三類：

  • 合併：把彼此重疊的區間黏成一個更大的區間（去除重疊、壓縮表示）。
  • 求交集：找出兩組區間共同覆蓋到的範圍（兩條行程表的空檔對齊）。
  • 統計同時重疊：算出在某個瞬間，最多有幾個區間同時存在（會議室數量、行程衝突）。

這三類表面操作不同，但共用同一個底層武器。

核心心法：先依 start 排序#

幾乎所有區間問題的第一步都是依起點排序。理由很簡單：排序後，任意相鄰的兩個區間都滿足「前者先開始」。一旦「誰先開始」被固定下來，重疊判定就能統一成一個式子——

對排序後的相鄰區間 A、B（A 先開始），只要 A.end >= B.start，兩者就重疊。

沒有排序時，你得分別討論誰在前誰在後；排序之後，這層討論被一次性消掉了，剩下的邏輯乾淨得多。

面試前先問清楚開閉區間

重疊判定到底是 A.end >= B.start 還是 A.end > B.start，取決於區間是閉區間還是開區間。例如 [1, 2] 與 [2, 3]：閉區間視為在端點 2 相接（算重疊），開區間則不算。動筆前先跟面試官確認端點語意，避免等號用錯而全盤皆輸。

三類經典操作#

合併區間 ↗#

依 start 排序後，逐一掃描。維護一個結果列表，每拿到一個新區間，就和結果中最後一個區間比較：

  • 若重疊（新區間的 start 不超過最後一個的 end），就把最後一個的右界更新成 max(兩者的 end)。
  • 若不重疊，直接把新區間加進結果列表。

因為已排序，只需要和「最後一個」比，不必回頭看更早的區間。

fun merge(intervals: Array<IntArray>): List<IntArray> {
    intervals.sortBy { it[0] }
    val result = mutableListOf<IntArray>()
    for (cur in intervals) {
        // 與結果中最後一個區間不重疊：開新區間
        if (result.isEmpty() || result.last()[1] < cur[0]) {
            result.add(cur)
        } else {
            // 重疊：擴張右界
            result.last()[1] = maxOf(result.last()[1], cur[1])
        }
    }
    return result
}

區間交集 ↗#

給兩個各自已排序的區間列表，求它們的交集。用雙指標分別指向兩列表的當前區間，每一步：

  • 交集是 [max(兩者 start), min(兩者 end)]；若 max(start) <= min(end) 則此交集有效，收進結果。
  • 推進「較早結束」的那一邊的指標——它已經沒有更多東西能和對方相交了。
fun intervalIntersection(a: Array<IntArray>, b: Array<IntArray>): List<IntArray> {
    val result = mutableListOf<IntArray>()
    var i = 0
    var j = 0
    while (i < a.size && j < b.size) {
        val lo = maxOf(a[i][0], b[j][0])
        val hi = minOf(a[i][1], b[j][1])
        if (lo <= hi) {
            result.add(intArrayOf(lo, hi))
        }
        // 較早結束的一邊往前推進
        if (a[i][1] < b[j][1]) i++ else j++
    }
    return result
}

最大重疊數 / 掃描線 (Sweep Line)#

問「同一時刻最多有幾個區間重疊」（會議室 II ↗）時，不要再以整段區間為單位思考，而是拆成事件點：每個區間 [start, end] 變成兩個事件——start 是「+1」（有人進場），end 是「−1」（有人離場）。把所有事件點排序後從左到右掃，維護一個計數器，遇 start 就 +1、遇 end 就 −1，掃描過程中計數器出現過的最大值，就是最多同時重疊的數量。

端點相同時的處理順序也受開閉區間影響：若一個會議在 t 結束、另一個在 t 開始，當作能無縫接續（不算重疊）時，應先處理 end（−1）再處理 start（+1）。

fun minMeetingRooms(intervals: Array<IntArray>): Int {
    val n = intervals.size
    val starts = intervals.map { it[0] }.sorted()
    val ends = intervals.map { it[1] }.sorted()

    var rooms = 0
    var maxRooms = 0
    var i = 0
    var j = 0
    while (i < n) {
        if (starts[i] < ends[j]) {
            // 有會議開始，且尚無會議在此前結束：需要一間房
            rooms++
            maxRooms = maxOf(maxRooms, rooms)
            i++
        } else {
            // 有會議結束，釋放一間房
            rooms--
            j++
        }
    }
    return maxRooms
}

小結#

操作前置處理關鍵步驟
合併區間依 start 排序與結果最後一個比較，重疊則取 max(end)，否則新增
區間交集兩列表各自已排序雙指標掃，交集為 [max(start), min(end)]，推進較早結束者
最大重疊數拆 start/end 事件並排序掃描線：遇 start +1、遇 end −1，取過程中最大值

三類操作的共同地基都是排序——把「誰先開始」固定下來，後續判定才能化繁為簡。當問題從「壓縮重疊」走向「在重疊中做取捨」（如挑選最多不重疊區間），就會進一步用上貪心應用中的排程策略。

Backward 位圖 狀態抽象與狀態圖 Forward