The idea is pretty simple: first we sort the intervals in the ascending order of start; then we check for the overlapping of each pair of neighboring intervals. If they do, then return false; after we finish all the checks and have not returned false, just return true.
Sorting takes O(nlogn) time and the overlapping checks take O(n) time, so this idea isO(nlogn) time in total.
The code is as follows.
1 class Solution { 2 public: 3 bool canAttendMeetings(vector<Interval>& intervals) { 4 sort(intervals.begin(), intervals.end(), compare); 5 int n = intervals.size(); 6 for (int i = 0; i < n - 1; i++) 7 if (overlap(intervals[i], intervals[i + 1])) 8 return false; 9 return true; 10 } 11 private: 12 static bool compare(Interval& interval1, Interval& interval2) { 13 return interval1.start < interval2.start; 14 } 15 bool overlap(Interval& interval1, Interval& interval2) { 16 return interval1.end > interval2.start; 17 } 18 };
原文：http://www.cnblogs.com/jcliBlogger/p/4713035.html