Simple O(nlogn) C++ solution using idea from "maximum overlapping intervals" problem


  • 1
    E

    This problem is an abstraction of the classic problem "maximum overlapping intervals" that appears in every elementary algorithm class. No idea why no similar solution appears on the list of high-vote posts. Or is there any flaw in this approach compared to others?

    class Solution {
    public:
        int minMeetingRooms(vector<Interval>& intervals) {
            vector<pair<int, int>> times;
            for (Interval& i : intervals) {
                times.push_back(make_pair(i.start, 1));
                times.push_back(make_pair(i.end, -1));
            }
            sort(times.begin(), times.end());
            int counter = curr_max = 0;
            for (auto& p : times) {
                counter += p.second;
                curr_max = max(curr_max, counter);
            }
            return curr_max;
        }
    };
    

Log in to reply
 

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