Easy C++ Solution ⭐||Explanation✔|| Beats 93.24%🎯|| PLEASE UPVOTE ⬆
Intuition\n Describe your first thoughts on how to solve this problem. \nThe goal is to maximize the sum of values by attending at most two non-overlapping even
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe goal is to maximize the sum of values by attending at most two non-overlapping events. The problem boils down to efficiently finding the best combination of two events where one event ends before the other starts. Sorting the events by their end times and using binary search to locate the last non-overlapping event ensures we can solve the problem efficiently.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n#### 1. Sorting the Events:\n\n- First, sort the events by their end time. This allows us to efficiently find the latest non-overlapping event for any given event using binary search.\n#### 2. Precomputing Maximum Values:\n\n- Precompute an array ***maxUpTo*** where ***maxUpTo[i]*** represents the maximum value of any single event from the start up to the ***ith*** event.\n- This helps in efficiently calculating the sum of the current event\'s value with the best non-overlapping event.\n#### 3. Finding Non-Overlapping Events:\n\n- For each event i, use binary search to find the last event j such that the end time of event j is less than the start time of event i.\n- Add the value of event i to the best value up to j **(i.e., maxUpTo[j])**.\n#### 4. Updating the Maximum Value:\n\n- Track the maximum value obtained by attending either a single event or a combination of two non-overlapping events.\n#### 5. Return the Result:\n\n- The result is the maximum value obtained by considering all events.\n\n# Complexity\n- Time complexity:**O(nlogn)**\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:**O(n)**\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```cpp []\nclass Solution {\npublic:\n    int maxTwoEvents(vector<vector<int>>& events) {\n        sort(events.begin(), events.end(), [](const vector<int>& a, const vector<int>& b) {\n        return a[1] < b[1];\n    });\n\n    int n = events.size();\n    vector<int> maxUpTo(n, 0); // Maximum value up to each event\n    int maxValue = 0;\n\n    // Precompute maxUpTo\n    maxUpTo[0] = events[0][2];\n    for (int i = 1; i < n; ++i) {\n        maxUpTo[i] = max(maxUpTo[i - 1], events[i][2]);\n    }\n\n    // Iterate over each event and compute the maximum value\n    for (int i = 0; i < n; ++i) {\n        int currValue = events[i][2];\n\n        // Find the latest non-overlapping event using binary search\n        int left = 0, right = i - 1, idx = -1;\n        while (left <= right) {\n            int mid = left + (right - left) / 2;\n            if (events[mid][1] < events[i][0]) {\n                idx = mid;\n                left = mid + 1;\n            } else {\n                right = mid - 1;\n            }\n        }\n\n        // Add the value of the best non-overlapping event\n        if (idx != -1) {\n            currValue += maxUpTo[idx];\n        }\n\n        // Update the maximum value\n        maxValue = max(maxValue, currValue);\n    }\n\n    return maxValue;\n    }\n};\n```
['Array', 'Binary Search', 'Dynamic Programming', 'Sorting', 'Heap (Priority Queue)', 'C++']