給定一個會議時間區間的陣列
intervals，其中intervals[i] = [start_i, end_i]，判斷一個人是否能參加所有會議（即是否有任何區間重疊）。
Example:
Input: intervals = [[0,30],[5,10],[15,20]] Output: false
WARNING
此題為 LeetCode Premium 題目。以下解法基於題目描述撰寫。
Intuition
TIP
排序後檢查相鄰區間是否重疊，只要有一對重疊就回傳 false。
- 排序後只需要比較相鄰的區間
- 重疊條件：前一個會議的結束時間 > 下一個會議的開始時間
Approaches
1. Brute Force — O(n^2) / O(1)
- Idea: 檢查所有配對是否重疊
- Time:
O(n^2) - Space:
O(1)
class Solution {
fun canAttendMeetings(intervals: Array<IntArray>): Boolean {
for (i in intervals.indices) {
for (j in i + 1 until intervals.size) {
val a = intervals[i]
val b = intervals[j]
if (a[0] < b[1] && b[0] < a[1]) return false
}
}
return true
}
}⭐ 2. Sort and Check Adjacent — O(n log n) / O(1)
- Idea: 按起點排序，只需檢查相鄰區間是否重疊
- Time:
O(n log n) - Space:
O(1)— 不計排序空間
class Solution {
fun canAttendMeetings(intervals: Array<IntArray>): Boolean {
intervals.sortBy { it[0] }
for (i in 1 until intervals.size) {
if (intervals[i][0] < intervals[i - 1][1]) return false
}
return true
}
}🔑 Takeaways
- Pattern: 排序 + 相鄰比較 — 判斷區間集合是否有重疊的最簡單方法
- Key trick: 排序後只需比較相鄰區間，因為如果任意兩個區間重疊，排序後它們一定相鄰