Nlog(n), n extra space C++ solution, 600ms


  • 0
    S

    The idea is to separately sort the starts and ends.
    And go though them picking up the earlier one from either values.
    If a start happens before the earliest end, we need one more room.

    class Solution {
    public:
        int minMeetingRooms(vector<Interval>& intervals) {
            int n = intervals.size();
            if (n == 0) {
                return 0;
            }
            vector<int> starts(n);
            vector<int> ends(n);
            for (int i = 0; i < n; i++) {
                starts[i] = intervals[i].start;
                ends[i] = intervals[i].end;
            }
            sort(starts.begin(), starts.end());
            sort(ends.begin(), ends.end());
    
            int result = 0, count = 0;
            int i = 0, j = 0;
            while (true)    {
                if (i == n) {
                    break;
                }
                
                if (starts[i] < ends[j])   {
                    i++;
                    count++;
                } else {
                    j++;
                    count--;
                }
                result = max(result, count);
            }        
    
            return result;
        }
    };

Log in to reply
 

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