LeetCode 刷題日記
EP.17

EP.17 — Intervals：
先排序，再掃一遍

#56 Merge Intervals · #435 Non-overlapping Intervals · #253 Meeting Rooms II
— 所有區間題的共同鑰匙：按 start 排序

Joseph Chen

2026
12 min read
3 題精講

區間（Interval）題是 LeetCode 的一個獨立類型，出現頻率高、變化多， 但所有題目幾乎都藏著同一把鑰匙：先把區間按 start 排序，再用一次線性掃描解決問題。

排序之後，重疊判斷就變成只看「當前區間的 start 和前一個區間的 end」—— 不需要兩兩比較，複雜度從 O(n²) 降到 O(n log n)。

這篇用三道題把這個思路吃透。

前置：區間重疊的判斷條件

兩個區間 [a, b] 和 [c, d]（假設 a ≤ c）：

重疊：b ≥ c

[1, 4]
[1,4]
[3, 6]
[3,6]

b=4 ≥ c=3 → 重疊，合併後 [1,6]

不重疊：b < c

[1, 2]
[1,2]
[4, 6]
[4,6]

b=2 < c=4 → 不重疊，各自獨立

排序後為什麼只需要看相鄰的？

按 start 排序後，如果 i 和 i+2 重疊，那 i 和 i+1 一定也重疊（因為 start[i+1] ≤ start[i+2]）。 所以只要一個個和「前一個處理完的區間」比較就夠了，不需要兩兩比較所有組合。

🔗

Part 1 — Merge Intervals

#56 · Medium · 合併所有重疊的區間

題目

給一組區間陣列，合併所有重疊的區間，回傳不重疊的區間陣列。

Input: [[1,3],[2,6],[8,10],[15,18]]

Output: [[1,6],[8,10],[15,18]]

（[1,3] 和 [2,6] 重疊，合併成 [1,6]）

視覺化：排序後逐一掃描

排序前

[1,3]
[1,3]
[2,6]
[2,6]
[8,10]
[8,10]
[15,18]
[15,18]

排序後（已按 start 排好，結果一樣）→ 掃描合併

[1,6]
[1,6]合併
[8,10]
[8,10]
[15,18]
[15,18]

演算法步驟

1

按 start 排序

intervals.sort(key=lambda x: x[0])
2

把第一個區間加入 result

result = [intervals[0]]
3

逐一處理後面每個區間

和 result 最後一個比較：若重疊就更新 end（取較大值），否則直接 append
merge_intervals.py
def merge(intervals: list[list[int]]) -> list[list[int]]:
    intervals.sort(key=lambda x: x[0])   # 按 start 排序
    result = [intervals[0]]

    for start, end in intervals[1:]:
        last_end = result[-1][1]

        if start <= last_end:             # 重疊：start 在前一個 end 之前（或相等）
            result[-1][1] = max(last_end, end)   # 更新 end 為較大值
        else:                             # 不重疊：直接加入
            result.append([start, end])

    return result

# [[1,3],[2,6],[8,10],[15,18]] → [[1,6],[8,10],[15,18]]
⏱ Time: O(n log n)💾 Space: O(n)

為什麼更新 end 要取 max？

考慮 [[1,10],[2,3]]，後者完全被前者包含。 排序後處理 [2,3] 時，last_end=10 > end=3， 若直接用 end 更新就錯了。max(last_end, end) 確保不會縮短。

✂️

Part 2 — Non-overlapping Intervals

#435 · Medium · 最少移除幾個區間讓剩下的不重疊？

題目

給一組區間，找出需要移除的最少區間數量，使得剩餘的區間互不重疊。

Input: [[1,2],[2,3],[3,4],[1,3]]

Output: 1（移除 [1,3]，剩下三個互不重疊）

Greedy 直覺：遇到重疊，優先保留 end 較小的

遇到兩個重疊的區間，要移除哪一個？移除 end 較大的那個——因為 end 越大，它越可能和後面的區間繼續重疊，留著麻煩更多。 等價地：保留 end 最小的，讓「已確定的邊界」盡量靠左，給後面的區間更多空間。

按 end 排序後的掃描過程（input: [[1,2],[1,3],[2,3],[3,4]]）

[1,2]

加入，cur_end = 2

[1,3]

start=1 ≤ cur_end=2，重疊！移除（end 較大的 [1,3]）

[2,3]

start=2 ≤ cur_end=2，重疊！移除

[3,4]

start=3 > cur_end=2，不重疊，加入，cur_end = 4

移除 2 個 → 答案：2

⚠️ 這題按 end 排序，不是按 start！

按 end 排序是為了讓「最早結束的區間」優先被保留。 這和 Merge Intervals 的按 start 排序不同，是這題最容易搞錯的地方。 口訣：想保留最多區間 → 按 end 排序，貪心保留最早結束的。

non_overlapping_intervals.py
def eraseOverlapIntervals(intervals: list[list[int]]) -> int:
    intervals.sort(key=lambda x: x[1])   # 按 end 排序！
    removed = 0
    cur_end = float('-inf')              # 目前保留的最後一個區間的 end

    for start, end in intervals:
        if start < cur_end:              # 重疊（start 在 cur_end 之前）
            removed += 1                 # 移除這個（end 較大的，因為已排序）
            # cur_end 不更新：繼續保留前一個 end 較小的
        else:                            # 不重疊：保留，更新 cur_end
            cur_end = end

    return removed
⏱ Time: O(n log n)💾 Space: O(1)

為什麼 cur_end 用 -inf 初始化？

確保第一個區間一定被保留（start > -inf 永遠成立）。 也可以直接 cur_end = intervals[0][1] 從第二個開始，效果相同。

📅

Part 3 — Meeting Rooms II

#253 · Medium · 最少需要幾間會議室？

題目

給一組會議的時間區間，找出同時進行的會議最多有幾場，即最少需要幾間會議室。

intervals = [[0,30],[5,10],[15,20]]

→ 2（[0,30] 和 [5,10] 同時進行，需要 2 間）

解法一：Min-Heap（最直觀）

把「正在進行的會議的結束時間」放進 min-heap。 處理新會議時，如果 heap 頂端（最早結束的那場）已經結束，就可以釋放那間會議室， 否則就得開新房間。Heap 的大小就是當前需要的會議室數。

intervals = [[0,30],[5,10],[15,20]]，按 start 排序後掃描

[0,30]heap: [30]需要 1 間

Heap 空，直接開新房間，push end=30

[5,10]heap: [10, 30]需要 2 間

start=5 < heap[0]=30，有重疊，再開一間，push end=10

[15,20]heap: [20, 30]需要 2 間

start=15 > heap[0]=10，[5,10] 已結束，pop 10，push 20。房間數不變

meeting_rooms_ii_heap.py
import heapq

def minMeetingRooms(intervals: list[list[int]]) -> int:
    if not intervals:
        return 0

    intervals.sort(key=lambda x: x[0])   # 按 start 排序
    heap = []   # min-heap，存放「正在進行的會議的結束時間」

    for start, end in intervals:
        if heap and heap[0] <= start:
            # 最早結束的那場會議已結束，釋放會議室（替換成新的 end）
            heapq.heapreplace(heap, end)
        else:
            # 沒有可用的會議室，新開一間
            heapq.heappush(heap, end)

    return len(heap)   # heap 大小 = 最多同時進行的會議數
⏱ Time: O(n log n)💾 Space: O(n)

解法二：事件掃描線（更優雅）

把每個區間的 start 和 end 分開，視為「+1（有人進來）」和「-1（有人離開）」的事件， 排序後掃描，追蹤同時在場的最大人數。

事件列表（intervals=[[0,30],[5,10],[15,20]]）

t=0+1進入 [0,30]count=1
t=5+1進入 [5,10]count=2 ← max
t=10-1離開 [5,10]count=1
t=15+1進入 [15,20]count=2 ← max
t=20-1離開 [15,20]count=1
t=30-1離開 [0,30]count=0

重點：t=10 離開和 t=10 進入同一時刻，先處理離開（-1 在前）

meeting_rooms_ii_sweep.py
def minMeetingRooms(intervals: list[list[int]]) -> int:
    events = []
    for start, end in intervals:
        events.append((start, 1))    # 會議開始：+1
        events.append((end, -1))     # 會議結束：-1

    # 排序：同時刻時，-1（結束）排在 +1（開始）之前
    # 避免「上一場 10 點結束、下一場 10 點開始」被算成重疊
    events.sort(key=lambda x: (x[0], x[1]))

    count = 0
    max_rooms = 0
    for _, delta in events:
        count += delta
        max_rooms = max(max_rooms, count)

    return max_rooms
⏱ Time: O(n log n)💾 Space: O(n)

Min-Heap 解法適合

  • • 面試最常見，概念直觀
  • • 可以延伸追蹤「哪間房間被分配出去」
  • • heapq 操作 O(log n)

掃描線解法適合

  • • 程式碼更短、更優雅
  • • 延伸到「任意時刻有多少人在場」
  • • 概念通用，可解很多類似問題

三題統一對比

題目排序依據核心操作複雜度
#56 Merge Intervals按 start 升序重疊則更新 result 最後一個的 endO(n log n) / O(n)
#435 Non-overlapping按 end 升序重疊則移除（count++），保留 end 較小的O(n log n) / O(1)
#253 Meeting Rooms II按 start 升序min-heap 追蹤 end，heap size = 房間數O(n log n) / O(n)

記憶口訣

• 合併區間（Merge）→ 按 start 排，更新 end 取 max

• 最少移除（Non-overlapping）→ 按 end 排，貪心保留最早結束的

• 最多房間（Meeting Rooms II）→ 按 start 排 + min-heap 追蹤 end，或掃描線 +1/-1

這篇學到什麼

🔑所有區間題的共同鑰匙：先排序（按 start 或 end），再一次線性掃描，複雜度 O(n log n)
🔗#56 Merge Intervals：按 start 排，重疊就更新 result 最後一個的 end（取 max 避免縮短）
✂️#435 Non-overlapping：按 end 排，遇到重疊移除 end 較大的，保留最早結束的區間
📅#253 Meeting Rooms II：min-heap 追蹤進行中會議的 end，heap size 就是所需房間數
⚡掃描線法（+1/-1 事件）是更通用的框架，可解「任意時刻同時進行幾件事」類問題

上一篇

EP.16 — Greedy

Jump Game、Gas Station

下一篇

EP.18 — Monotonic Stack

Daily Temperatures、Next Greater

LeetCode
Intervals
Merge
Greedy
Heap
掃描線
Python
EP.17