Two Best Non-Overlapping Events

Problem

You are given a 0-indexed 2D integer array of events where events[i] = [startTimei, endTimei, valuei]. The ith event starts at startTimei and ends at endTimei, and if you attend this event, you will receive a value of valuei. You can choose at most two non-overlapping events to attend such that the sum of their values is maximized.

Return this maximum sum.

Note that the start time and end time is inclusive: that is, you cannot attend two events where one of them starts and the other ends at the same time. More specifically, if you attend an event with end time t, the next event must start at or after t + 1.

Examples

Example 1:

gantt
    title Jobs
    dateFormat X
    axisFormat %s
    section Event 0
    value = 2   : 0, 3
    section Event 1
    value = 2   : 3, 5
    section Event 2
    value = 3   : done, 1, 4

1
2
3
Input: events = [[1,3,2],[4,5,2],[2,4,3]]
Output: 4
Explanation: Choose the green events, 0 and 1 for a sum of 2 + 2 = 4.

Example 2:

gantt
    title Jobs
    dateFormat X
    axisFormat %s
    section Event 0
    value = 2   : done, 0, 3
    section Event 1
    value = 2   : done, 3, 5
    section Event 2
    value = 5   : 0, 5

1
2
3
Input: events = [[1,3,2],[4,5,2],[1,5,5]]
Output: 5
Explanation: Choose event 2 for a sum of 5.

Example 3:

gantt
    title Jobs
    dateFormat X
    axisFormat %s
    section Event 0
    value = 3   : 0, 5
    section Event 1
    value = 1   : 0, 5
    section Event 2
    value = 5   : 5, 6

1
2
3
Input: events = [[1,5,3],[1,5,1],[6,6,5]]
Output: 8
Explanation: Choose events 0 and 2 for a sum of 3 + 5 = 8.

Solution

Method 1 - Sorting + DP + Binary Search

Here is the approach:

Sort Events:
- First, sort the events based on their end times to facilitate the use of binary search for finding non-overlapping events.
Dynamic Programming:
- Use a dp array where dp[i] represents the maximum value obtainable by considering events up to the i-th event.
- Use an auxiliary array max_value to keep track of the maximum value obtainable considering only one event up to i.
Binary Search:
- To quickly find the latest event that does not overlap with the current event, use binary search.
Calculate Maximum Value:
- Iterate through events and for each event, use the dp and max_value arrays to decide the best outcome by either including the current event alone or including it with a previously non-overlapping event.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
    public int maxTwoEvents(int[][] events) {
        Arrays.sort(events, (a, b) -> Integer.compare(a[1], b[1]));
        int n = events.length;
        int[] dp = new int[n];
        int[] max_value = new int[n];
        
        dp[0] = events[0][2];
        max_value[0] = events[0][2];
        for (int i = 1; i < n; i++) {
            dp[i] = Math.max(dp[i - 1], events[i][2]);
            int idx = binarySearch(events, events[i][0]);
            if (idx != -1) {
                dp[i] = Math.max(dp[i], events[i][2] + max_value[idx]);
            }
            max_value[i] = Math.max(max_value[i - 1], events[i][2]);
        }
        return dp[n - 1];
    }

    private int binarySearch(int[][] events, int startTime) {
        int low = 0, high = events.length - 1;

        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (events[mid][1] < startTime) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return high;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution:
    def maxTwoEvents(self, events: List[List[int]]) -> int:
        events.sort(key=lambda x: x[1])
        n = len(events)
        dp = [0] * n
        max_value = [0] * n
        
        dp[0] = events[0][2]
        max_value[0] = events[0][2]
        
        # Helper function for binary search
        def find_latest_non_overlap(idx: int) -> int:
            left, right = 0, idx - 1
            while left <= right:
                mid = left + (right - left) // 2
                if events[mid][1] < events[idx][0]:
                    left = mid + 1
                else:
                    right = mid - 1
            return right
        
        for i in range(1, n):
            # Include this event only
            dp[i] = max(dp[i - 1], events[i][2])
            # Include this event and the best non-overlapping event
            idx = find_latest_non_overlap(i)
            if idx != -1:
                dp[i] = max(dp[i], events[i][2] + max_value[idx])
            max_value[i] = max(max_value[i - 1], events[i][2])
        
        return dp[-1]

Complexity

⏰ Time complexity: O(n log n)
- Sorting the events: O(n log n)
- Processing each event with binary search: O(n log n)
🧺 Space complexity: O(n) for the dp and max_value arrays.

Problem#

Examples#

Solution#

Method 1 - Sorting + DP + Binary Search#

Code#

Complexity#