meeting-rooms

252. Meeting Rooms

Given an array of meeting time intervals where intervals[i] = [starti, endi], determine if a person could attend all meetings.

Example 1:

Input: intervals = [[0,30],[5,10],[15,20]] Output: false

Example 2:

Input: intervals = [[7,10],[2,4]] Output: true

Constraints:

• 0 <= intervals.length <= 104
• intervals[i].length == 2
• 0 <= starti < endi <= 106

算區間是否重疊，如果重疊 return false

class Solution {
public:
    bool canAttendMeetings(vector<vector<int>>& intervals) {
        int n = intervals.size();
        if (n == 0) return true;
        sort(intervals.begin(), intervals.end());
        for(int i = 0; i < n - 1; i++) {
            // 如果目前區間的 endtime 比下一個區間的 start time 大的話
            // 代表有 overlap
            if (intervals[i].back() > intervals[i + 1].front())
                return false;
        }
        return true;
    }
};

• T: $O(N \cdot \log N)$，取決於排序演算法
• S: $O(1)$