LeetCode 2054: Two Best Non-Overlapping Events Solution

Master LeetCode problem 2054 (Two Best Non-Overlapping Events), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

2054. Two Best Non-Overlapping Events

Medium

Array Binary Search Dynamic Programming Sorting Heap (Priority Queue)

Problem Explanation

Explanation

To solve this problem, we can use dynamic programming. We will sort the events based on their end times. Then, we will iterate through the events and for each event, we have two options: either attend it or skip it. If we attend the current event, we need to find the best non-overlapping event before it. By keeping track of the maximum value we can get by attending one event before the current event, we can calculate the maximum value we can get by attending the current event.

We will maintain two arrays to store the maximum values we can get by attending one event before the current event and the maximum values we can get by attending the current event. At each step, we update these arrays based on the current event.

Finally, the maximum value we can get will be the maximum of the values in these arrays.

Time Complexity: O(nlogn) where n is the number of events
Space Complexity: O(n)

Solution Code

class Solution {
    public int maxValue(int[][] events) {
        Arrays.sort(events, (a, b) -> a[1] - b[1]);
        
        int n = events.length;
        int[] prevMax = new int[n];
        int[] currMax = new int[n];
        
        prevMax[0] = events[0][2];
        
        for (int i = 1; i < n; i++) {
            prevMax[i] = Math.max(prevMax[i - 1], events[i][2]);
        }
        
        for (int i = 0; i < n; i++) {
            int prev = i > 0 ? prevMax[i - 1] : 0;
            int j = i - 1;
            while (j >= 0 && events[j][1] >= events[i][0]) j--;
            currMax[i] = Math.max(prev, (j >= 0) ? prevMax[j] + events[i][2] : events[i][2]);
        }
        
        int result = 0;
        for (int max : currMax) {
            result = Math.max(result, max);
        }
        
        return result;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 2054 (Two Best Non-Overlapping Events)?

This page provides optimized solutions for LeetCode problem 2054 (Two Best Non-Overlapping Events) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 2054 (Two Best Non-Overlapping Events)?

The time complexity for LeetCode 2054 (Two Best Non-Overlapping Events) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 2054 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 2054 in Java, C++, or Python.

Back to LeetCode Solutions