Two Best Non-overlapping Events - Easy Solution - 🌟 Nice Explanation 🌟
Intuition\n\n1. Sort the 2-D array events with respect to the start_time so we can compare the end time of previous element in the array with the elements in ot
# Intuition\n\n1. Sort the 2-D array events with respect to the start_time so we can compare the end time of previous element in the array with the elements in other index greater than the previous index.\n\n1. Use suffixMax to calculate the maximum value that can be obtained at each index.\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n\n**Initialization and pre-work**:\n\nInitialize no_events to be the no of elements in the events array.\n\n    int no_events=events.length;\n\nSort the events array with respect to the startTime which is at 0-th index at each events.\n\n    Arrays.sort(events,(a,b)->a[0]-b[0]);\n\nInitialize suffixMax as integer array with the length of the events array.\n \n    int[] suffixMax=new int[no_events];\n\nInitialize suffixMax last element as last value of the events array which is sorted by start index.\n\n    suffixMax[no_events-1]=events[no_events-1][2];\n\n**Find the maximum value at each index from last**:\n\nIterate through each elements of the events array from the last index of the array and suffixMax is calculated by finding the maximum value of the nextIndex and the current Index\'s value.\n\n    for(int i=no_events-2;i>=0;i--)\n    {\n        suffixMax[i]=Math.max(suffixMax[i+1],events[i][2]);\n    }\n\n**Find the maximum value by attending atmost two events**:\n\nInitialize maxSum to be zero.\n\n    int maxSum=0;\n\nIterate through all the elements of the events array.\n\n    for(int i=0;i<no_events;i++){\n\n**Binary Search to find nextEventIndex**:\n\nUse binary search to find the next non-overlapping element with the highest value by initializing the left index to be index + 1 (i+1) and the right index to be no_events - 1 , then also nextEventIndex to be -1.\n\n    int left=i+1,right=no_events-1;\n    int nextEventIndex=-1;\n\nIterate from left till the left is less than the right index.\n\n    while(left<=right){\n\nFind the mid value by mid=left+(right-left)/2.\n\n    int mid=left+(right-left)/2;\n\nCheck if the events[mid][0]>events[i][2] which indicates the non-overlapping index.So the nextEventIndex is updated as mid and the next element can be between left to right=mid-1.\n\n    if(events[mid][0]>events[i][1])\n    {\n        nextEventIndex=mid;\n        right=mid-1;\n    }\n\nOtherwise, find the nextIndex from left=mid+1 to right.\n\n   else\n    {\n        left=mid+1;\n    }\n\n**nextEventIndex is valid or not**:\n\nAt the end of the binary search, if the nextEventIndex is valid,Find the maxSum which is the maximum of the maxSum and the current value plus the maximum value at the index nextEventIndex.\n\n    if(nextEventIndex!=-1)\n    {\n        maxSum=Math.max(maxSum,events[i][2]+suffixMax[nextEventIndex]);\n    }\n\nFinally, maxSum to be the maximum of the maxSum and the value of the current event index.\n\n    maxSum=Math.max(maxSum,events[i][2]);\n\n**Returning the value**:\n\nThe maxSum contains the maximum value that can be obtained by choosing atmost two non-overlapping events.\n\n    return maxSum;\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- ***Time complexity***: **O(nlogn)**.\n      n -> number of elements in the events array.\n\n**Sorting Events**: **O(nlogn)**.\n\nThe events are sorted based on **their start times**: **O(nlogn)**.\n\n**Building suffixMax**: **O(n)**.\n\nCalculating the maximum suffix values involves a **single reverse traversal** of the events array: O(n).\n\n**Finding Non-Overlapping Event Using Binary Search**: **O(nlogn)**.\n\nFor each event (n), binary search is performed to find the next non-overlapping event: O(logn) per event.\n\n**Updating maxSum**: **O(n)**.\n\nEach event is checked to **update maxSum: O(n)**.\n\n**Overall Time Complexity**: **O(nlogn)**.\n\nHence the overall Time Complexity can be \n**O(nlogn) + O(n) + O(nlogn)=O(nlogn)**.\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- ***Space complexity***: **O(n)**.\n    n -> number of elements in the events array.\n\n**Suffix Array**: **O(n)**.\n\nThe suffixMax array requires **O(n) space**.\n\n**Other Variables**: **O(1)**.\n\nA few scalar variables like **maxSum, left, right, etc.: O(1)**.\n\n**Overall Space Complexity**: **O(n)**.\n\nHence overall space complexity is O(n) which is dominated by the **suffixMax array**.\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```java []\nclass Solution {\n    public int maxTwoEvents(int[][] events) {\n        int no_events=events.length;\n        Arrays.sort(events,(a,b)->a[0]-b[0]);\n\n        int[] suffixMax=new int[no_events];\n        suffixMax[no_events-1]=events[no_events-1][2];\n\n        for(int i=no_events-2;i>=0;i--)\n        {\n            suffixMax[i]=Math.max(suffixMax[i+1],events[i][2]);\n        }\n        int maxSum=0;\n        for(int i=0;i<no_events;i++)\n        {\n            int left=i+1,right=no_events-1;\n            int nextEventIndex=-1;\n\n            while(left<=right)\n            {\n                int mid=left+(right-left)/2;\n                if(events[mid][0]>events[i][1])\n                {\n                    nextEventIndex=mid;\n                    right=mid-1;\n                }\n                else\n                {\n                    left=mid+1;\n                }\n            }\n            if(nextEventIndex!=-1)\n            {\n                maxSum=Math.max(maxSum,events[i][2]+suffixMax[nextEventIndex]);\n            }\n            maxSum=Math.max(maxSum,events[i][2]);\n        }\n        return maxSum;\n    }\n}\n```
['Array', 'Binary Search', 'Sorting', 'Java']