Java Solution for Two Best Non-Overlapping Events Problem
Intuition\n Describe your first thoughts on how to solve this problem. \nThe problem is to find the maximum sum of values of two non-overlapping events. To solv
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe problem is to find the maximum sum of values of two non-overlapping events. To solve it efficiently:\n\u2022\tWe leverage the timeline of events by breaking them into start and end points.\n\u2022\tBy sweeping through these points in sorted order, we dynamically maintain the maximum value of a single event (maxValue) seen so far.\n\u2022\tWhenever we encounter a new event\u2019s start, we combine its value with maxValue to check if it forms the maximum sum of two non-overlapping events.\n\nThis approach ensures that we process all events in a structured manner without explicitly checking every pair of events, avoiding an O(n^2) complexity.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1.\tEvent Breakdown:\n\t\u2022\tFor each event [start, end, value], split it into two key time points:\n\t\u2022\tA start point (start, 1, value) indicating when the event begins.\n\t\u2022\tAn end point (end + 1, 0, value) indicating when the event ends (end time is inclusive, so we use end + 1).\n\t\u2022\tAdd these points to a list times.\n2.\tSorting:\n\t\u2022\tSort times primarily by the time value.\n\t\u2022\tIf two points have the same time, prioritize end points (type 0) over start points (type 1). This ensures proper updates when events overlap.\n3.\tSweep Line Algorithm:\n\t\u2022\tInitialize:\n\t\u2022\tmaxValue: Tracks the maximum value of a single event seen so far.\n\t\u2022\tans: Tracks the maximum sum of two non-overlapping events.\n\t\u2022\tProcess each point in times:\n\t\u2022\tIf it\u2019s a start point (type == 1), calculate the maximum sum of two events as:\n\t\u2022\tvalue + maxValue (current event + best event seen so far).\n\t\u2022\tUpdate ans with the maximum value of ans and this sum.\n\t\u2022\tIf it\u2019s an end point (type == 0), update maxValue to be the maximum of its current value and the event\u2019s value.\n4.\tResult:\n\t\u2022\tAfter processing all points, ans will contain the maximum sum of two non-overlapping events.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n1.\tEvent Processing:\n\t\u2022\tSplitting each event into two points takes O(n), where n is the number of events.\n\t\u2022\tSorting the times array takes O(2n log (2n)) = O(n log n), since it contains 2n elements.\n\t\u2022\tSweeping through times takes O(2n) = O(n).\n2.\tOverall: O(n log n) due to the sorting step.\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n1.\tAdditional Data Structures:\n\t\u2022\tThe times list contains 2n elements, requiring O(n) space.\n\t\u2022\tNo other significant space is used.\n2.\tOverall: O(n).\n\n# Code\n```java []\nclass Solution {\n    public int maxTwoEvents(int[][] events) {\n        List<int[]> times = new ArrayList<>();\n\n        for (int[] event : events) {\n            times.add(new int[]{event[0], 1, event[2]}); \n            times.add(new int[]{event[1] + 1, 0, event[2]}); \n        }\n\n        times.sort((a, b) -> (a[0] == b[0]) ? Integer.compare(a[1], b[1]) : Integer.compare(a[0], b[0]));\n\n        int ans = 0;\n        int maxValue = 0;\n\n        for (int[] time : times) {\n            if (time[1] == 1) {\n                ans = Math.max(ans, time[2] + maxValue);\n            } else {\n                maxValue = Math.max(maxValue, time[2]);\n            }\n        }\n\n        return ans;\n    }\n}\n```
['Java']