Complete Detailed Explanation || Most Intuitive Linear DP + Binary Search Solution || C++ ||
Intuition\nFirst Thing WE can understand from the problem is to sort the events first for getting non-overlapping two events. \nThen we can calculate the upperb
# Intuition\nFirst Thing WE can understand from the problem is to sort the events first for getting **non-overlapping** two events. \nThen we can calculate the upperbound for current event ending time for choosing next event.\n\n# Approach\nAs mentioned in the intuition we first sort the array.\nThen Here we can observe nonlinearity in the **values** associated with the events.\nExample : events = [[1,3,2],[4,5,2],[1,5,5]]\nAfter Sorting the events became\nevents=[[1,3,2],[1,5,5],[4,5,2]]\nThe Values of Events are in non monotonic nature [2,5,2]\n**Important Observation :**\nconsider the events = [[1,3,2],[4,5,2],[6,7,3],[8,10,100],[11,12,1],[13,20,5]] (arranged in sorted order)\nConsider If we Select the first event now sum=2\nthen what is the next possible event that we can choose OR what are the options we have to choose\n- we can choose event 2 with value 2\n- we can choose event 3 with value 3\n- **we can choose event 4 with value 100**\n- we can choose event 5 with value 1\n- we can choose event 5 with value 5\nWhat is Best Option to choose for getting maximum Sum?\nwe have to choose event 4 .\nwhat can we understand from above example ,\nafter selecting event-1 =[1,3,2]\nthe next should start after ending time of event -1 \nhence events are sorted we can apply upperbound on ending time for getting next event .\nHere for event 1 ending time=3\nupperbound(events,3) = index 1\nwhich form index 1 to n-1 we can select any one event which result maximum sum.\nfor getting that particular event we can precompute the maximum values from the r.h.s **because we don\'t care about which event it was , we just need the maximum value of the event**\nlets compute the maxvalues from the right hand side\ndeclare a maxValues/(u can declare as dp if you wish to) array of size =events.size.\nRun the loop from n-1 to 0\nuse currentMax Variable initialize with zero\n1. at index = 5 ,  events value = 5 && currentMax=0 \nhence currentMax is less than event value assign \n currentMax=events[index][2] and then \nmaxValues[index]=currentMax\n2.at index = 4 ,  events value = 1 && currentMax=5 \nhence currentMax is greater than event value we don\'t change currentMax value just assign \nmaxValues[index]=currentMax\n3. at index = 3 ,  events value = 100 && currentMax=5\nhence currentMax is less than event value assign \n currentMax=events[index][2] and then \nmaxValues[index]=currentMax\nFrom here onwards currentMax value will not get changed \nafter completion for maxValues Computation \nthe maxValues/DP array = [100,100,100,100,5,5]\nNow After Selecting the first event sum=2\nand upperbound(events,endtime) = index 1\nand maxValue[1]=100\nHence For event 1 maximum sum = 102\nLike we can compute maximum sum for every event and return the maximum sum among them.\n**I WISH YOU UNDERSTOOD MY EXPLANATION \n  PLEASE UPVOTE IF YOU LIKE MY SOLUTION**\n\n![upvote.jpg](https://assets.leetcode.com/users/images/48e5d6ec-7d8f-4ae9-80c1-2017bec466dc_1689422474.1885724.jpeg)\n# Complexity\n- Time complexity:\n O(NLOGN) for sorting the events \nand we run a loop which for calculating maximum sum runs **n** times in which we use upperbound everytime the loop runs which tooks **logn** time \nhence its results in overall  O(nlogn) time complexity\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nO(N) for storing the precomputed maximum values\n\n# Code\n```\nclass Solution {\npublic:\n    int upper_bound(vector<vector<int>>& events,int key,int size)\n    {\n        int low=0,high=size-1,mid;\n        while(low<=high)\n        {\n            mid=(low+high)/2;\n            if(events[mid][0]>key) high=mid-1;\n            else low=mid+1;\n        }\n        return low;\n    }\n    int maxTwoEvents(vector<vector<int>>& events) {\n        sort(events.begin(),events.end());\n        int size=events.size(),currMax=0;\n        vector<int>maxValue(size,0); //you can declare it as dp\n        //now precompute the maximum values\n\n        for(int i=size-1;i>=0;i--)\n        {\n            currMax=max(currMax,events[i][2]);\n            maxValue[i]=currMax;\n        }\n        int maxTwoEventss=0,currTwoEvents=0,nextInd;\n        for(int i=0;i<size;i++)\n        {\n             currTwoEvents=events[i][2];\n             nextInd=upper_bound(events,events[i][1],size);\n             if(nextInd<size) currTwoEvents+=maxValue[nextInd];\n             maxTwoEventss=max(maxTwoEventss,currTwoEvents);\n        }\n           return maxTwoEventss;\n    }\n};\n```
['Binary Search', 'Dynamic Programming', 'C++']