2 Approaches, loop + Binary Search || Easy to understand || with Explaination
Intuition\nQuestion asked to select at most 2 events which are not colliding with each other. We can select one in first for loop and try for all other events i
# Intuition\nQuestion asked to select **at most 2** events which are not colliding with each other. We can select one in first for loop and try for all other events if they collide with current event, if it doesn\'t collide, we can save maximum of all answers, but this will take O(n^2) time which will lead to time limit excedded.\n\nTo reduce time complexity to O(nlogn) we can select one as previous approach but instead of searching all over the events again, we can use Binary Search, As we know binary search needs sorted array , we can sort array based on initial time.\n\nHow will sorting help based on initial time? now after sorting we can get the lower bound of event start time which is **just greater than** the end time of the selected event. So from this event which we have got by Binary search, all events ahead can have possible maximum event value, hence now we need to keep track of highest value of event till event i from event[n-1].\n\n# Approach\n- Sort all events based on initial value to compare end time of selected one with the next events start time later in binary search.\n- Compute and store the highest value of event from ith event till end event.\n- Using for loop select all events one by one and find lower bound event index which have value just greater than the current selected event.\n- Save as selectedValue + maxvalue ahead from lower bound using already computed maxValue array answer if it have greater value than previous answer.\n- It might be possible that we can\'t be getting the lower bound, so in this case it can be possible that the current event have value greater than any two other not colliding events, hence consider the individual values as well ,remember line from description **at most 2 events** \n# Complexity\n- Time complexity:\nApplying binary search(log(n)) of each element(n elements)\n=> $$O(nlogn)$$\n\n- Space complexity:\nTime taken by precompute is the only extra space taken of size n\n=> $$O(n)$$\n\n# Code\n```cpp []\n/// LOOP + Binarysearch\nclass Solution {\npublic:\n    int binary(vector<vector<int>>& events,int i,int j,int curr){\n        int idx = -1;\n\n        while(i<=j){\n            int mid = i + (j-i)/2;\n\n            if(events[mid][0] > events[curr][1]){\n                idx = mid;\n                j = mid-1;\n            }else i = mid+1;\n        }\n        return idx;\n    }\n    int maxTwoEvents(vector<vector<int>>& events) {\n        int n = events.size();\n\n        sort(events.begin(),events.end());\n\n        vector<int>postcompute(n,0);\n\n        postcompute[n-1] = events[n-1][2];\n\n        for(int i=n-2;i>=0;i--)\n            postcompute[i] = max(events[i][2],postcompute[i+1]);\n        \n        int ans = 0;\n        for(int i=0;i<n;i++){\n            int rightIdx = binary(events,i+1,n-1,i);\n            if(rightIdx != -1)\n                ans = max(ans,events[i][2]+postcompute[rightIdx]);\n            \n            ans = max(ans,events[i][2]);\n        }\n        return ans;\n    }\n};\n```\n# Bonus Approach - Recursion + Memo + Binary Search\n\n```cpp []\n//Recursion + Memo + Binary Search\nclass Solution {\npublic:\n    int n;\n    int dp[100001][3];\n    int binary(vector<vector<int>>& events,int end){\n        int i=0,j=n-1,ans = n;\n        while(i<=j){\n            int mid = i+(j-i)/2;\n            if(events[mid][0]>end){\n                ans = mid;\n                j = mid-1;\n            }else i = mid+1;\n        }\n        return ans;\n    }\n    int solve(vector<vector<int>>& events,int i,int count){\n        if(count == 2 || i>=n)\n            return 0;\n        if(dp[i][count]!=-1)\n            return dp[i][count];\n        int nextidx = binary(events,events[i][1]);\n        int take = events[i][2] +solve(events,nextidx,count+1);\n        int nottake = solve(events,i+1,count);\n        return dp[i][count] = max(take,nottake);\n    }\n    int maxTwoEvents(vector<vector<int>>& events) {\n        n = events.size();\n        memset(dp,-1,sizeof(dp));\n        sort(events.begin(),events.end());\n        return solve(events,0,0);\n    }\n};\n```
['Binary Search', 'Dynamic Programming', 'Sorting', 'C++']