Description
給定一個會議時間區間的陣列
intervals，其中intervals[i] = [start_i, end_i]，判斷一個人是否能參加所有會議（即是否有任何區間重疊）。
Example:
Input: intervals = [[0,30],[5,10],[15,20]] Output: false
此題為 LeetCode Premium 題目。以下解法基於題目描述撰寫。
Intuition#
排序後檢查相鄰區間是否重疊，只要有一對重疊就回傳 false。
- 排序後只需要比較相鄰的區間
- 重疊條件：前一個會議的結束時間 > 下一個會議的開始時間
Approaches#
1: Brute Force#
- 概念: 檢查所有配對是否重疊
- 時間複雜度:
O(n^2) - 空間複雜度:
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)— 不計排序空間
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: 排序 + 相鄰比較 — 判斷區間集合是否有重疊的最簡單方法
- 關鍵技巧: 排序後只需比較相鄰區間，因為如果任意兩個區間重疊，排序後它們一定相鄰