Multiple Approaches | Heap Based || DP + Binary Search || C++ Clean Code
Approach 1: Sorting + Priority Queue\n\nThis approach is best suited when we have just "at most 2" events to attend.\n\n# Code : \n\n\nint maxTwoEvents(vector<v
**Approach 1: Sorting + Priority Queue**\n\nThis approach is best suited when we have just **"at most 2"** events to attend.\n\n# Code : \n\n```\nint maxTwoEvents(vector<vector<int>>& events) {\n        \n\tint n = events.size();\n\n\tpriority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;  //  <endTime, value>\n\n\tsort(events.begin(), events.end());\n\n\tint maxVal = 0, maxSum = 0;\n\n\tfor(auto& event : events) {\n\t\twhile(pq.size() && pq.top().first < event[0]) {\n\t\t\tmaxVal = max(maxVal, pq.top().second);\n\t\t\tpq.pop();\n\t\t}\n\n\t\tmaxSum = max(maxSum, maxVal + event[2]);\n\n\t\tpq.push({event[1], event[2]});\n\t}\n\n\treturn maxSum;\n}\n```\n\n**Complexity:**\n\n* **Time** : `O(N log N + 2N)` ,\n\t* `N log N` : Sorting and Priority Queue\n\t* `2N` : Since we are poping events from heap to process, so each events is processed twice.\n\t\n* **Space** : `O(N)`, storing events into heap\n\n----------------------------------------------------------------------------------------------------------------------------\n\n**Follow Up Question** : How will you solve this problem when you can attend **at most K** events? \n\nWe cannot use previous approach if we have K events to attend. So how we will solve this? \nLets look at another approach !!\n\n----------------------------------------------------------------------------------------------------------------------------\n\n**Approach 2: DP(Memoization) + Binary Search**\n\n\n# Code: \n\n```\nclass Solution {\npublic:\n        \n    int getNextIndex(vector<vector<int>>& events, int idx, const int& n) {\n        \n        int endTime = events[idx][1];\n        \n        int lo = idx+1, hi = n-1;\n        \n        int ans = n;\n        \n        while(lo <= hi) {\n            int mid = (lo + hi) >> 1;\n            \n            if(events[mid][0] > endTime) {\n                ans = mid;\n                hi = mid-1;\n            }\n            else {\n                lo = mid+1;\n            }\n        }\n        \n        return ans;\n    }\n    \n    int attendEvents(vector<vector<int>>& events, vector<vector<int>>& dp, int idx, int k, const int& n) {\n        if(k == 0 || idx == n) return 0;\n        \n        if(dp[idx][k] != -1) return dp[idx][k];\n        \n        // Include : attend current event\n        int nextIdx = getNextIndex(events, idx, n); \n\n        int incl = events[idx][2] + attendEvents(events, dp, nextIdx, k-1, n);\n        \n        // Exclude : skip current event\n        int excl = attendEvents(events, dp, idx+1, k, n);\n        \n        return dp[idx][k] = max(incl, excl);\n    }\n    \n    int maxTwoEvents(vector<vector<int>>& events) {\n        \n        int n = events.size(), k = 2;\n        sort(events.begin(), events.end());\n        \n        \n        vector<vector<int>> dp(n+1, vector<int>(k+1, -1));\n    \n        return attendEvents(events, dp, 0, k, n);\n    }\n};\n```\n**Complexity:**\n\n* **Time** : `O(N log N)` , sorting , attending events and searching for next nearest event\n* **Space** : `O(N * k)`, for memoization \n\n\n----------------------------------------------------------------------------------------------------------------------------\n\n**Similar Problems :**\n\n* [Maximum Earnings from Taxi](https://leetcode.com/problems/maximum-earnings-from-taxi/)\n* [Maximum Profit Job Scheduling](https://leetcode.com/problems/maximum-profit-in-job-scheduling/)\n\n***If you find this post helpful, do give it a like :)***
['Dynamic Programming', 'Memoization', 'C', 'Heap (Priority Queue)', 'Binary Tree']