C++, O(nlogn), 9ms, 10 lines

  • 0
    1. sort the array by meeting start time ascending to mimic a serials of chronological events.
    2. create a min heap (priority queue) by the end time. the queue represents the concurrently happening meetings at a given time.
    3. loop through the array, for each meeting:
    • pop all the meetings in the heap that finishes earlier than the incoming meeting's start time, because at the time of the new meeting, they have already finished, therefore doesn't need a meeting room.
    • add the incoming meeting to the heap.
    • the minimal room required is the maximal items in the priority queue, meaning the concurrently occurring meetings.
    int minMeetingRooms(vector<Interval>& intervals) {
            sort(intervals.begin(), intervals.end(), [](const Interval& lhs, const Interval& rhs){return lhs.start < rhs.start;});
            priority_queue<Interval, vector<Interval>, auto(*)(const Interval&, const Interval&)->bool> q([](const Interval& lhs, const Interval& rhs)->bool{return lhs.end > rhs.end;});
            int rooms = 0;
            for(const Interval& i : intervals)
                while(!q.empty() && q.top().end<=i.start) q.pop();
                rooms = max(rooms, (int)q.size());
            return rooms;

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.