LeetCode [252] Meeting Rooms

 252. Meeting Rooms

Easy

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

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

//C++: 588ms /** * Definition for an interval. * struct Interval { * int start; * int end; * Interval() : start(0), end(0) {} * Interval(int s, int e) : start(s), end(e) {} * }; */ bool comp(const Interval &a, const Interval &b){ return a.start<b.start; } class Solution { public: bool canAttendMeetings(vector<interval>& intervals) { sort(intervals.begin(), intervals.end(), comp); for(int i=1; i<intervals.size(); ++i){ if(intervals[i].start<intervals[i-1].end) return false; } return true; } };

YMSF

第一轮： 蠡口兒吴饵的变种。给一列interval 和一个新的interval，看新的interval有没有和之前的有conflict。 Followup 是 如果给的一列的interval是sorted，如何提高时间复杂度。 当时的想法是binary search.

应该是sorted by start time吧 然后binary search找这个interval应该插入到哪里，找到以后看它和它前面的和后面的intervals是否有相交。