leetcode-253. Meeting Rooms II

Given an array of meeting time intervals consisting of start and end times [[s1,e1],[s2,e2],…] (si < ei), find the minimum number of conference rooms required.

For example,
Given [[0, 30],[5, 10],[15, 20]],
return 2.
原题地址

跟上一道题差不多的思路，我的代码如下：

/**
 * Definition for an interval.
 * struct Interval {
 *     int start;
 *     int end;
 *     Interval() : start(0), end(0) {}
 *     Interval(int s, int e) : start(s), end(e) {}
 * };
 */
 struct comp{
    bool operator() (Interval itv1, Interval itv2) {
        return itv1.start < itv2.start;
    }
 };
class Solution {
public:
    int minMeetingRooms(vector<Interval>& intervals) {
        sort(intervals.begin(), intervals.end(), comp());
        //building a vector indicates the ending time of each room
        //if a new inteval's start time < all ending time, add a new ending time to the vector
        vector<int> rooms;
        for (Interval& itv : intervals) {
            bool addRoom = true;
            for (int i = 0; i < rooms.size(); i++) {
                if (itv.start >= rooms[i]) {
                    rooms[i] = itv.end;
                    addRoom = false;
                    break;
                }
            }
            if (addRoom) {
                rooms.push_back(itv.end);
            }
        }
        return rooms.size();
    }
};

在网上看到一个更好的思路，统计当前时间有多少会议开着。更加简洁明了。

/**
 * 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:
    int minMeetingRooms(vector<Interval>& intervals) {
        vector<pair<int, int>> changes;
        for (auto i : intervals) {
            changes.push_back({i.start, 1});
            changes.push_back({i.end, -1});
        };
        sort(begin(changes), end(changes));
        int rooms = 0, maxrooms = 0;
        for (auto change : changes)
            maxrooms = max(maxrooms, rooms += change.second);
        return maxrooms;
    }
};