Mind palace

some thoughts

0%

252. Meeting Rooms

Posted on Edited on In Disqus:
Symbols count in article: 1.9k Reading time ≈ 2 mins.

O(nlogn) time O(n) space
要clarify一下start和end如果重合怎么算

1
2
3
4
5
6
7
8
9
10
class Solution {
public:
    bool canAttendMeetings(vector<vector<int>>& intervals) {
        sort(begin(intervals), end(intervals));
        for (int i = 1; i < size(intervals); ++i) {
            if (intervals[i - 1][1] > intervals[i][0]) return false;
        }
        return true;
    }
};
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) {
        auto cmp = [](const Interval &a, const Interval &b) {return a.start < b.start;};
        sort(begin(intervals), end(intervals), cmp);
        for (int i = 1; i < intervals.size(); ++i) {
            if (intervals[i - 1].end > intervals[i].start) return false;
        }
        return true;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * 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) {
        auto cmp = [](const Interval &a, const Interval &b) {return a.start < b.start;};
        sort(begin(intervals), end(intervals), cmp);
        int end = -1;
        for (const auto &i : intervals) {
            if (i.start < end) return false;
            end = i.end;
        }
        return true;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
/**
 * 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) {
        map<int, int> m;
        for (const auto &i : intervals) {
            ++m[i.start];
            --m[i.end];
        }
        int cnt = 0;
        for (auto &&p : m) {
            cnt += p.second;
            if (cnt > 1) return false;
        }
        return true;
    }
};