FXTi's blog
0%

meeting-rooms

Posted on Edited on

Meeting Rooms – LeetCode 252

Problem

Description

Given an array of meeting time intervals consisting of start and end times

[[s1,e1],[s2,e2],…] (si < ei), determine if a person could attend all meetings.

Answer

Original

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
 * Definition for an interval.
 * struct Interval {
 *     int start;
 *     int end;
 *     Interval() : start(0), end(0) {}
 *     Interval(int s, int e) : start(s), end(e) {}
 * };
 */
class Solution {
public:
    bool canAttendMeetings(vector<Interval>& intervals) {
		for(unsigned i = 0; i != intervals.size(); ++i){
			for(unsigned j = i + 1; j != intervals.size(); ++j){
				if(intervals[i].start < intervals[j].end && intervals[j].start < intervals[i].end) return false;
			}
		}
        return true;
    }
};

思路

循环遍历进行检查，时间复杂度$O(n^2)$，空间复杂度$O(1)$。

Better

思路

先对数列进行排序然后一次遍历完成检查。时间复杂度$O(nlog{n})$，空间复杂度$O(1)$。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
 * Definition for an interval.
 * struct Interval {
 *     int start;
 *     int end;
 *     Interval() : start(0), end(0) {}
 *     Interval(int s, int e) : start(s), end(e) {}
 * };
 */
class Solution {
public:
    bool canAttendMeetings(vector<Interval>& intervals) {
		sort(intervals.begin(),intervals.end(),
			[](Interval &i1,Interval &i2){return i1.start < i2.start;});
		for(vector<Interval>::iterator i = intervals.begin();i < intervals.end() - 1; ++i){
			if(i->end > (i+1)->start) return false;
		}
		return true;
    }
};