C++ | Sorting + Priority Queue | DP+ Binary Search
Solution 1: Sorting + Priority Queue\n\nSteps:\n1. First sort the events on basis of their starting time .\n2. We will use priority queue to store events that h
### Solution 1: Sorting + Priority Queue\n\n**Steps:**\n1. First sort the events on basis of their starting time .\n2. We will use priority queue to store events that have started before the current event.\n3. Elements in priority queue are of type vector {minus of endTime , startTime , value} (ordered by endTime i.e element that finishes first is at top).\n4. Instead of using min heap, I have stored minus of endTime.\n5. We will use a variable maxVal to store maximum value so far.\n\n```\nint maxTwoEvents(vector<vector<int>>& events) {\n        sort(events.begin(),events.end());\n        int maxVal = 0;\n        \n        priority_queue<vector<int>> pq;\n        int ans = 0;\n        \n        for(auto e : events){\n            while(!pq.empty() and ((-pq.top()[0]) < e[0])){\n                maxVal = max(maxVal , pq.top()[2]);\n                pq.pop();\n            }\n            ans = max(ans , e[2]+maxVal);\n            pq.push({(-e[1]) , e[0] , e[2]});\n        }\n        return ans;\n    }\n```\n\nTime Complexity : O(nlogn), as each element will be pushed and poped only once in priority queue.\nSpace Complexity: O(n)\n\n### Solution 2: Recursion + Binary Search\nWe have 2 choices : Either attend a particular event or don\'t attend.\n```\nclass Solution {\n    int func(int ind , int eventsAttended , vector<vector<int>>& events){\n        //base case\n        if(ind == events.size() || eventsAttended == 2){\n            return 0;\n        }\n        \n        //Choice 1 : attend this event\n        vector<int> tempVec = {events[ind][1] , INT_MAX , INT_MAX};\n        int nextInd = upper_bound(events.begin() , events.end() , tempVec) - events.begin(); //find index of next event whose start time is greater than ending time of current event\n        int val1 = events[ind][2] + func(nextInd , eventsAttended+1 , events);\n        \n        //Choice 2: don\'t attend\n        int val2 = func(ind+1 , eventsAttended , events);\n        \n        return max(val1 , val2);\n    }\n    \npublic:\n    int maxTwoEvents(vector<vector<int>>& events) {\n        sort(events.begin() , events.end());\n        \n        return func(0,0,events);\n    }\n};\n```\n\nThis solution will lead to TLE.\n\n### Solution 3: Recursion + Memoization\n\n```\nclass Solution {\n    int func(int ind , int eventsAttended , vector<vector<int>>& events , vector<vector<int>>& dp){\n        //base case\n        if(ind == events.size() || eventsAttended == 2){\n            return 0;\n        }\n        \n        if(dp[ind][eventsAttended] != -1)\n            return dp[ind][eventsAttended];\n        \n        //Choice 1 : attend this event\n        vector<int> tempVec = {events[ind][1] , INT_MAX , INT_MAX};\n        int nextInd = upper_bound(events.begin() , events.end() , tempVec) - events.begin();\n        int val1 = events[ind][2] + func(nextInd , eventsAttended+1 , events,dp);\n        \n        //Choice 2: don\'t attend\n        int val2 = func(ind+1 , eventsAttended , events,dp);\n        \n        return dp[ind][eventsAttended] = max(val1 , val2);\n    }\n    \npublic:\n    int maxTwoEvents(vector<vector<int>>& events) {\n        sort(events.begin() , events.end());\n        int n = events.size();\n        \n        vector<vector<int>> dp(n , vector<int>(2 , -1));\n        return func(0,0,events,dp);\n    }\n};\n```\n\n***Do Upvote if you find the solution helpful!***
['Dynamic Programming', 'C', 'Sorting', 'Heap (Priority Queue)', 'Binary Tree']