253. Meeting Rooms II

• Difficulty: Medium

• Topics: Heap, Greedy, Sort

• Similar Questions:

  • Merge Intervals

  • Meeting Rooms

  • Minimum Number of Arrows to Burst Balloons

  • Car Pooling

Problem:

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

Example 1:

Input: [[0, 30],[5, 10],[15, 20]]
Output: 2

Example 2:

Input: [[7,10],[2,4]]
Output: 1

NOTE: input types have been changed on April 15, 2019. Please reset to default code definition to get new method signature.

Solutions:

class Solution {
public:
    struct MeetingEvent {
        int time;
        bool start;

        MeetingEvent(int time, bool start) {
            this->time = time;
            this->start = start;
        }

        bool operator< (const MeetingEvent& event) const {
            if (this->time == event.time) {
                return !(this->start);
            } else {
                return this->time < event.time;
            }
        }
    };

    int minMeetingRooms(vector<vector<int>>& intervals) {
        vector<MeetingEvent> events;
        for (auto& interval : intervals) {
            events.push_back({interval[0], true});
            events.push_back({interval[1], false});
        }

        sort(events.begin(), events.end());
        int count = 0;
        int ret = 0;
        for (int i = 0; i < events.size(); ++i) {
            if (events[i].start) {
                ++count;
                ret = max(ret, count);
            } else {
                --count;
            }
        }

        return ret;
    }
};