Easy Solution | O(nlogn) | Priority Queue | Maximum Sum
Intuition\n Describe your first thoughts on how to solve this problem. \nThe key idea is to sort the events by their start times and use a priority queue to tra
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe key idea is to sort the events by their start times and use a priority queue to track the maximum value of events that end before the current event\'s start time. This allows us to efficiently determine the best event to pair with the current event.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1. Sort Events: Sort the events by their start time to process them in order.\n2. Priority Queue: Use a priority queue (min-heap) to store the end times and values of events. This helps us efficiently track the maximum value of events that don\'t overlap with the current event.\n3. Iterate Through Events: For each event:\n    - Pop events from the queue that end before the current event\'s start time and update the maximum value.\n    - Calculate the potential maximum sum by combining the current event\'s value with the maximum value from previous non-overlapping events.\n    - Push the current event into the queue.\n4. Track Maximum Sum: Update the answer with the maximum sum found so far.\n\n# Complexity\n- Time complexity: O(nlogn)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nSorting the events takes O(nlogn). Processing each event with a priority queue operation takes O(logn), leading to an overall complexity of O(nlogn).\n\n- Space complexity: O(n)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nThe space complexity is O(n) due to the priority queue.\n\n# Code\n```python []\nimport heapq\n\nclass Solution:\n    def maxTwoEvents(self, events):\n        events.sort()  # Sort by start time\n        pq = []  # Priority queue to store (end_time, value)\n        max_value = 0\n        ans = 0\n        \n        for start, end, value in events:\n            # Remove all events that end before the current event\'s start time\n            while pq and pq[0][0] < start:\n                max_value = max(max_value, heapq.heappop(pq)[1])\n            \n            # Update the maximum sum of values\n            ans = max(ans, max_value + value)\n            \n            # Push the current event into the priority queue\n            heapq.heappush(pq, (end, value))\n        \n        return ans\n```\n```cpp []\n#include <vector>\n#include <queue>\n#include <algorithm>\n\nusing namespace std;\n\nclass Solution {\npublic:\n    int maxTwoEvents(vector<vector<int>>& events) {\n        sort(events.begin(), events.end()); // Sort events by start time\n        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;\n        int maxVal = 0, ans = 0;\n\n        for (auto& event : events) {\n            int start = event[0], end = event[1], value = event[2];\n\n            // Remove events that end before the current event\'s start time\n            while (!pq.empty() && pq.top().first < start) {\n                maxVal = max(maxVal, pq.top().second);\n                pq.pop();\n            }\n\n            // Update the maximum sum of values\n            ans = max(ans, maxVal + value);\n\n            // Add the current event to the priority queue\n            pq.push({end, value});\n        }\n\n        return ans;\n    }\n};\n```\n```java []\nimport java.util.*;\n\nclass Solution {\n    public int maxTwoEvents(int[][] events) {\n        Arrays.sort(events, (a, b) -> Integer.compare(a[0], b[0]));\n        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> Integer.compare(a[0], b[0]));\n        int maxVal = 0, ans = 0;\n        \n        for (int[] event : events) {\n            int start = event[0], end = event[1], value = event[2];\n            \n            // Remove all events that end before the current event\'s start time\n            while (!pq.isEmpty() && pq.peek()[0] < start) {\n                maxVal = Math.max(maxVal, pq.poll()[1]);\n            }\n            \n            // Update the maximum sum of values\n            ans = Math.max(ans, maxVal + value);\n            \n            // Add the current event to the priority queue\n            pq.offer(new int[] {end, value});\n        }\n        \n        return ans;\n    }\n}\n```\n``` c []\n#include <stdio.h>\n#include <stdlib.h>\n\ntypedef struct {\n    int start, end, value;\n} Event;\n\nint compare(const void *a, const void *b) {\n    return ((Event *)a)->start - ((Event *)b)->start;\n}\n\ntypedef struct {\n    int end, value;\n} QueueNode;\n\nint maxTwoEvents(Event* events, int n) {\n    qsort(events, n, sizeof(Event), compare);\n    QueueNode* pq = (QueueNode*)malloc(sizeof(QueueNode) * n);\n    int size = 0, maxVal = 0, result = 0;\n\n    for (int i = 0; i < n; i++) {\n        while (size > 0 && pq[0].end < events[i].start) {\n            maxVal = pq[--size].value > maxVal ? pq[size].value : maxVal;\n        }\n        result = result > maxVal + events[i].value ? result : maxVal + events[i].value;\n        pq[size++] = (QueueNode){events[i].end, events[i].value};\n    }\n\n    free(pq);\n    return result;\n}\n```
['C', 'Sorting', 'Heap (Priority Queue)', 'C++', 'Java', 'Python3']