C++ solution 9ms


  • 0
    H

    First sort the vector by the start time. Then create another vector "ends" for collecting all the end times as we traverse through the intervals vector, and analyze each interval. The basic idea is: If interval A starts after interval B ends, we replace the end time of B with end time of A inside vector "ends", and update the result.

    public:
        int minMeetingRooms(vector<Interval>& intervals) {
            if (intervals.size() == 0) return 0;
            if (intervals.size() == 1) return 1;
            auto cmp = [](Interval a, Interval b) {return a.start < b.start;};
            sort(intervals.begin(), intervals.end(), cmp);
            int res = intervals.size();
            vector<int> ends;
            for (int i = 0; i < intervals.size(); i++) {
                if (i == 0) {
                    ends.push_back(intervals[i].end);
                    continue;
                }
                bool noExtra = false;
                for (int j = 0; j < ends.size(); j++) {
                    if (intervals[i].start >= ends[j]) {
                        ends.erase(ends.begin()+j);
                        ends.push_back(intervals[i].end);
                        noExtra = true;
                        res--;
                        break;
                    }
                }
                if (!noExtra) ends.push_back(intervals[i].end);
            }
            return res;
        }
    };

Log in to reply
 

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