Maximum Number of Events That Can Be Attended Solutions in C++

/// Source : https://leetcode.com/problems/maximum-number-of-events-that-can-be-attended/
/// Author : liuyubobobo
/// Time   : 2019-02-15

#include <iostream>
#include <vector>
#include <map>

using namespace std;


/// Using map to simulate priority queue
/// Time Complexity: O(t * logn)
/// Space Complexity: O(n)
class Solution {
public:
    int maxEvents(vector<vector<int>>& events) {

        map<pair<int, int>, int> q;
        for(const vector<int>& e: events)
            q[make_pair(e[0], e[1])] ++;

        int res = 0;
        for(int i = 0; i <= 100000 && !q.empty(); i ++){

            map<pair<int, int>, int>::iterator iter = q.begin();
            if(i >= iter->first.first && i <= iter->first.second){
                res ++;
                iter->second --;
                if(iter->second == 0) q.erase(iter);

                vector<pair<int, int>> v;
                for(map<pair<int, int>, int>::iterator iter = q.begin(); iter != q.end(); iter ++)
                    if(iter->first.first <= i)
                        v.push_back(iter->first);
                    else
                        break;

                for(const pair<int, int>& p: v){
                    int num = q[p];
                    q.erase(p);
                    if(i + 1 <= p.second){
                        pair<int, int> newp = make_pair(i + 1, p.second);
                        if(q.count(newp)) q[newp] += num;
                        else q[newp] = num;
                    }
                }
            }
        }
        return res;
    }
};


int main() {

    vector<vector<int>> events1 = {{1, 2}, {2, 3}, {3, 4}, {1, 2}};
    cout << Solution().maxEvents(events1) << endl;
    // 4

    vector<vector<int>> events2 = {{1, 4}, {4, 4}, {2, 2}, {3, 4}, {1, 1}};
    cout << Solution().maxEvents(events2) << endl;
    // 4

    vector<vector<int>> events3 = {{1, 5}, {1, 5}, {1, 5}, {2, 3}, {2, 3}};
    cout << Solution().maxEvents(events3) << endl;
    // 5

    vector<vector<int>> events4 = {{7, 11}, {7, 11}, {7, 11}, {9, 10}, {9, 11}};
    cout << Solution().maxEvents(events4) << endl;
    // 5

    return 0;
}

/// Source : https://leetcode.com/problems/maximum-number-of-events-that-can-be-attended/
/// Author : liuyubobobo
/// Time   : 2019-02-17

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

using namespace std;


/// Using priority queue
/// Time Complexity: O(t * logn)
/// Space Complexity: O(n)
class Solution {
public:
    int maxEvents(vector<vector<int>>& events) {

        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
        for(const vector<int>& e: events)
            pq.push(make_pair(e[0], e[1]));

        int res = 0;
        for(int i = 0; i <= 100000 && !pq.empty(); i ++){

            pair<int, int> e = pq.top();
            if(i >= e.first && i <= e.second){
                res ++;
                pq.pop();

                while(!pq.empty() && pq.top().first <= i){
                    pair<int, int> t = pq.top();
                    pq.pop();
                    if(i + 1 <= t.second){
                        t.first = i + 1;
                        pq.push(t);
                    }
                }
            }
        }
        return res;
    }
};


int main() {

    vector<vector<int>> events1 = {{1, 2}, {2, 3}, {3, 4}, {1, 2}};
    cout << Solution().maxEvents(events1) << endl;
    // 4

    vector<vector<int>> events2 = {{1, 4}, {4, 4}, {2, 2}, {3, 4}, {1, 1}};
    cout << Solution().maxEvents(events2) << endl;
    // 4

    vector<vector<int>> events3 = {{1, 5}, {1, 5}, {1, 5}, {2, 3}, {2, 3}};
    cout << Solution().maxEvents(events3) << endl;
    // 5

    vector<vector<int>> events4 = {{7, 11}, {7, 11}, {7, 11}, {9, 10}, {9, 11}};
    cout << Solution().maxEvents(events4) << endl;
    // 5

    return 0;
}

/// Source : https://leetcode.com/problems/maximum-number-of-events-that-can-be-attended/
/// Author : liuyubobobo
/// Time   : 2019-02-17

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

using namespace std;


/// Using priority queue to only record the end date
/// Time Complexity: O(t * logn)
/// Space Complexity: O(n)
class Solution {
public:
    int maxEvents(vector<vector<int>>& events) {

        sort(events.begin(), events.end());

        priority_queue<int, vector<int>, greater<int>> pq;

        int res = 0, e = 0;
        for(int i = 0; i <= 100000; i ++){
            while(e < events.size() && events[e][0] == i) pq.push(events[e ++][1]);
            while(!pq.empty() && pq.top() < i) pq.pop();
            if(!pq.empty()) res ++, pq.pop();
        }
        return res;
    }
};


int main() {

    vector<vector<int>> events1 = {{1, 2}, {2, 3}, {3, 4}, {1, 2}};
    cout << Solution().maxEvents(events1) << endl;
    // 4

    vector<vector<int>> events2 = {{1, 4}, {4, 4}, {2, 2}, {3, 4}, {1, 1}};
    cout << Solution().maxEvents(events2) << endl;
    // 4

    vector<vector<int>> events3 = {{1, 5}, {1, 5}, {1, 5}, {2, 3}, {2, 3}};
    cout << Solution().maxEvents(events3) << endl;
    // 5

    vector<vector<int>> events4 = {{7, 11}, {7, 11}, {7, 11}, {9, 10}, {9, 11}};
    cout << Solution().maxEvents(events4) << endl;
    // 5

    return 0;
}