Meeting Rooms II Solutions in C++

/// Source : https://leetcode.com/problems/meeting-rooms-ii/description/
/// Author : liuyubobobo
/// Time   : 2018-09-10

#include <iostream>
#include <vector>

using namespace std;


/// Simulation
/// Time Complexity: O(n^2)
/// Space Complexity: O(n)

/// Definition for an interval.
struct Interval {
    int start;
    int end;
    Interval() : start(0), end(0) {}
    Interval(int s, int e) : start(s), end(e) {}
};

class Solution {

public:
    int minMeetingRooms(vector<Interval>& intervals) {

        sort(intervals.begin(), intervals.end(), cmpIntervals);

        vector<Interval> rooms;
        int sz = 0, res = 0;
        for(const Interval& meeting: intervals){

            for(Interval& room: rooms)
                if(room.end != -1 && room.end <= meeting.start){
                    room.start = room.end = -1;
                    sz --;
                }

            bool ok = false;
            for(Interval& room: rooms)
                if(room.start == -1){
                    room = meeting;
                    ok = true;
                    break;
                }
            if(!ok)
                rooms.push_back(meeting);
            sz ++;

            res = max(res, sz);
        }

        return res;
    }

private:
    static bool cmpIntervals(const Interval& i1, const Interval& i2){
        if(i1.start != i2.start)
            return i1.start < i2.start;
        return i1.end < i2.end;
    }
};


int main() {

    return 0;
}

/// Source : https://leetcode.com/problems/meeting-rooms-ii/description/
/// Author : liuyubobobo
/// Time   : 2018-09-10

#include <iostream>
#include <vector>
#include <queue>

using namespace std;


/// Simulation
/// Using Priority Queue
///
/// Time Complexity: O(nlogn)
/// Space Complexity: O(n)

/// Definition for an interval.
struct Interval {
    int start;
    int end;
    Interval() : start(0), end(0) {}
    Interval(int s, int e) : start(s), end(e) {}
};

class Solution {

private:
    class CompareInterval{
    public:
        bool operator()(const Interval& a, const Interval& b){
            return a.end > b.end;
        }
    };

public:
    int minMeetingRooms(vector<Interval>& intervals) {

        sort(intervals.begin(), intervals.end(), cmpIntervals);

        priority_queue<Interval, vector<Interval>, CompareInterval> rooms;
        int res = 0;
        for(const Interval& meeting: intervals){

            while(!rooms.empty() && rooms.top().end <= meeting.start)
                rooms.pop();

            rooms.push(meeting);
            res = max(res, (int)rooms.size());
        }

        return res;
    }

private:
    static bool cmpIntervals(const Interval& i1, const Interval& i2){
        if(i1.start != i2.start)
            return i1.start < i2.start;
        return i1.end < i2.end;
    }
};


int main() {

    return 0;
}

/// Source : https://leetcode.com/problems/meeting-rooms-ii/description/
/// Author : liuyubobobo
/// Time   : 2018-09-10

#include <iostream>
#include <vector>

using namespace std;


/// Two Pointers
/// Sorting start time and end time seperately.
///
/// Time Complexity: O(nlogn)
/// Space Complexity: O(n)

/// Definition for an interval.
struct Interval {
    int start;
    int end;
    Interval() : start(0), end(0) {}
    Interval(int s, int e) : start(s), end(e) {}
};

class Solution {
public:
    int minMeetingRooms(vector<Interval>& intervals) {

        if(intervals.size() == 0)
            return 0;

        vector<int> starts, ends;
        for(const Interval& interval: intervals){
            starts.push_back(interval.start);
            ends.push_back(interval.end);
        }
        sort(starts.begin(), starts.end());
        sort(ends.begin(), ends.end());


        int res = 1, sz = 1;
        int end_index = 0;
        for(int start_index = 1; start_index < starts.size(); start_index ++){
            while(end_index < ends.size() && ends[end_index] <= starts[start_index])
                end_index ++, sz --;
            sz ++;
            res = max(res, sz);
        }

        return res;
    }
};


int main() {

    return 0;
}

/// Source : https://leetcode.com/problems/meeting-rooms-ii/description/
/// Author : liuyubobobo
/// Time   : 2018-09-10

#include <iostream>
#include <vector>

using namespace std;


/// Dealing with start time and end time seperately
/// make start time and end time in a pair structure
/// and deal with them in one single vector:)
///
/// Time Complexity: O(nlogn)
/// Space Complexity: O(n)

/// Definition for an interval.
struct Interval {
    int start;
    int end;
    Interval() : start(0), end(0) {}
    Interval(int s, int e) : start(s), end(e) {}
};

class Solution {
public:
    int minMeetingRooms(vector<Interval>& intervals) {

        vector<pair<int, char>> timepoints;
        for(const Interval& interval: intervals){
            timepoints.push_back(make_pair(interval.start, 's'));
            timepoints.push_back(make_pair(interval.end, 'e'));
        }
        sort(timepoints.begin(), timepoints.end());

        int res = 0;
        int cur = 0;
        for(const pair<int, char>& p: timepoints)
            if(p.second == 's'){
                cur ++;
                res = max(res, cur);
            }
            else
                cur --;

        return res;
    }
};


int main() {

    return 0;
}