題目描述:給定一組會議時間區間,判斷一個人是否能參加所有會議(即區間之間不重疊)。
解題思路:按開始時間排序,然後檢查相鄰區間是否重疊:若某個會議的開始時間早於上一個會議的結束時間,則存在衝突,回傳 false。完全遍歷無衝突則回傳 true。
時間複雜度:O(n log n) — 排序主導。
空間複雜度:O(1) — 原地排序,只用迴圈變數。
1. Sort intervals by start time 2. For i from 1 to n-1: a. If intervals[i].start < intervals[i-1].end: return false 3. Return true
掃描線 O(n log n):標記會議開始和結束事件,排序後掃描 — 同複雜度,對某些變種更靈活。
檢查所有配對 O(n²):暴力檢查每一對會議是否重疊 — 簡單但低效。