LeetCode 2054 - Two Best Non-Overlapping Events

The problem gives us a list of events, where each event is represented as: Each event occupies an inclusive time interval from startTime to endTime. If we attend that event, we earn value points. We are allowed to attend at most two events, but the chosen events must not overlap.

leetcodemediumarraybinary-searchdynamic-programmingsortingheap-(priority-queue)

LeetCode Problem 2054

Difficulty: 🟡 Medium
Topics: Array, Binary Search, Dynamic Programming, Sorting, Heap (Priority Queue)

Solution

Problem Understanding

The problem gives us a list of events, where each event is represented as:

[startTime, endTime, value]

Each event occupies an inclusive time interval from startTime to endTime. If we attend that event, we earn value points.

We are allowed to attend at most two events, but the chosen events must not overlap. Since the intervals are inclusive, two events conflict if one starts exactly when the other ends. In other words:

  • If an event ends at time t
  • The next event must start at time t + 1 or later

The goal is to maximize the total value collected from up to two non-overlapping events.

The input size is large:

  • Up to 10^5 events
  • Time values can be as large as 10^9

These constraints immediately rule out any algorithm that checks all event pairs directly in quadratic time.

A few important observations:

  • We may choose only one event if that produces the maximum value.
  • Multiple events can share the same start or end times.
  • Because intervals are inclusive, an event ending at time 5 cannot be paired with another starting at 5.
  • The large coordinate range means we cannot use timeline simulation or prefix arrays indexed by time.

The core challenge is efficiently finding, for each event, the best compatible event that starts strictly after its end time.

Approaches

Brute Force Approach

The most straightforward solution is to try every possible pair of events.

For each event i, we compare it with every other event j:

  • Check whether the two events overlap
  • If they do not overlap, compute value[i] + value[j]
  • Also consider taking only one event

This guarantees correctness because every valid combination is examined.

However, the time complexity is far too large.

With n = 10^5, checking all pairs requires:

O(n^2) = 10^10

operations in the worst case, which is not feasible.

Key Insight

The important observation is that once events are sorted by start time, we can efficiently search for the next compatible event using binary search.

Suppose we are currently considering event:

[start, end, value]

We want to quickly find:

the first event whose start time > end

If we already knew the maximum event value available from every future position onward, then we could instantly compute:

current value + best compatible future value

This leads to an efficient strategy:

  1. Sort events by start time
  2. Build a suffix maximum array
  3. Use binary search to locate the next non-overlapping event

This reduces the complexity to O(n log n).

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(n²) O(1) Checks every pair of events
Optimal O(n log n) O(n) Sorting + binary search + suffix maximum

Algorithm Walkthrough

Optimal Algorithm

  1. Sort all events by their start time.

Sorting allows us to binary search for future compatible events efficiently. After sorting, all candidate future events appear to the right of the current event. 2. Extract all start times into a separate array.

This array enables binary search. For each event, we want to find the first event whose start time is strictly greater than the current event's end time. 3. Build a suffix maximum array.

Let:

suffixMax[i]

represent the maximum event value among all events from index i to the end.

This means once we locate the next compatible event index, we can instantly know the best possible future event value. 4. Iterate through each event.

For every event:

  • Treat it as the first chosen event
  • Use binary search to find the first compatible future event
  • Combine the current value with the best future value
  • Update the global maximum
  1. Also consider taking only one event.

Since we may choose at most two events, not exactly two, the best answer might consist of a single high-value event.

Why it works

The algorithm works because for every event, we consider all valid second-event candidates indirectly.

Binary search guarantees we locate the earliest non-overlapping future event. Since the suffix maximum array stores the best value from that point onward, we do not need to scan every future event individually.

Thus, every valid two-event combination is evaluated efficiently, and the maximum possible value is found.

Python Solution

from bisect import bisect_right
from typing import List

class Solution:
    def maxTwoEvents(self, events: List[List[int]]) -> int:
        # Sort events by start time
        events.sort(key=lambda event: event[0])

        n = len(events)

        # Store all start times separately for binary search
        start_times = [event[0] for event in events]

        # suffix_max[i] = maximum event value from i to end
        suffix_max = [0] * n
        suffix_max[-1] = events[-1][2]

        for i in range(n - 2, -1, -1):
            suffix_max[i] = max(suffix_max[i + 1], events[i][2])

        answer = 0

        for i in range(n):
            start, end, value = events[i]

            # Find first event with start time > end
            next_index = bisect_right(start_times, end)

            current_total = value

            # Add best compatible future event if it exists
            if next_index < n:
                current_total += suffix_max[next_index]

            answer = max(answer, current_total)

        return answer

The implementation begins by sorting events according to their start times. This ordering is essential because binary search requires sorted data.

Next, we build a separate start_times array. Instead of repeatedly extracting start times during binary search, we store them once for efficiency and clarity.

The suffix_max array is then constructed from right to left. Each position stores the maximum value available from that index onward. This allows constant-time lookup of the best future event.

For each event, we use bisect_right to locate the first event whose start time is strictly greater than the current event's end time. This correctly handles the inclusive interval rule.

If a compatible future event exists, we combine the current event's value with the best future value from suffix_max. Otherwise, we simply consider the current event alone.

The maximum across all possibilities is returned.

Go Solution

package main

import (
	"sort"
)

func maxTwoEvents(events [][]int) int {
	// Sort by start time
	sort.Slice(events, func(i, j int) bool {
		return events[i][0] < events[j][0]
	})

	n := len(events)

	// Extract start times
	startTimes := make([]int, n)
	for i := 0; i < n; i++ {
		startTimes[i] = events[i][0]
	}

	// Build suffix maximum array
	suffixMax := make([]int, n)
	suffixMax[n-1] = events[n-1][2]

	for i := n - 2; i >= 0; i-- {
		if suffixMax[i+1] > events[i][2] {
			suffixMax[i] = suffixMax[i+1]
		} else {
			suffixMax[i] = events[i][2]
		}
	}

	answer := 0

	for i := 0; i < n; i++ {
		end := events[i][1]
		value := events[i][2]

		// Find first index with start time > end
		nextIndex := sort.Search(n, func(j int) bool {
			return startTimes[j] > end
		})

		currentTotal := value

		if nextIndex < n {
			currentTotal += suffixMax[nextIndex]
		}

		if currentTotal > answer {
			answer = currentTotal
		}
	}

	return answer
}

The Go solution follows the same algorithmic structure as the Python version.

Instead of Python's bisect_right, Go uses sort.Search to perform binary search. The search condition finds the first start time strictly greater than the current event's end time.

Go slices naturally handle dynamic arrays, so no special handling for empty structures is required here because the constraints guarantee at least two events.

All arithmetic safely fits within Go's int type under the problem constraints.

Worked Examples

Example 1

Input:

events = [[1,3,2],[4,5,2],[2,4,3]]

Step 1: Sort by start time

Index Event
0 [1,3,2]
1 [2,4,3]
2 [4,5,2]

Step 2: Build start times array

start_times = [1, 2, 4]

Step 3: Build suffix maximum array

Working backward:

Index Event Value suffix_max
2 2 2
1 3 3
0 2 3

Final:

suffix_max = [3, 3, 2]

Step 4: Process each event

Current Event end Binary Search Result Best Future Value Total
[1,3,2] 3 index 2 2 4
[2,4,3] 4 none 0 3
[4,5,2] 5 none 0 2

Maximum total:

4

Example 2

Input:

events = [[1,3,2],[4,5,2],[1,5,5]]

Sorted Events

Index Event
0 [1,3,2]
1 [1,5,5]
2 [4,5,2]

start_times

[1, 1, 4]

suffix_max

Index suffix_max
2 2
1 5
0 5

Processing

Current Event Compatible Index Total
[1,3,2] 2 4
[1,5,5] none 5
[4,5,2] none 2

Maximum:

5

Example 3

Input:

events = [[1,5,3],[1,5,1],[6,6,5]]

Sorted Events

Index Event
0 [1,5,3]
1 [1,5,1]
2 [6,6,5]

start_times

[1, 1, 6]

suffix_max

Index suffix_max
2 5
1 5
0 5

Processing

Current Event Compatible Index Total
[1,5,3] 2 8
[1,5,1] 2 6
[6,6,5] none 5

Maximum:

8

Complexity Analysis

Measure Complexity Explanation
Time O(n log n) Sorting dominates, each event also performs binary search
Space O(n) Start times array and suffix maximum array

The sorting step requires O(n log n) time. After sorting, we process each event once, and each iteration performs a binary search in O(log n) time.

The total complexity therefore remains:

O(n log n)

Additional memory is used for:

  • The start_times array
  • The suffix_max array

Both require linear space.

Test Cases

from typing import List

class Solution:
    def maxTwoEvents(self, events: List[List[int]]) -> int:
        from bisect import bisect_right

        events.sort(key=lambda event: event[0])

        n = len(events)

        start_times = [event[0] for event in events]

        suffix_max = [0] * n
        suffix_max[-1] = events[-1][2]

        for i in range(n - 2, -1, -1):
            suffix_max[i] = max(suffix_max[i + 1], events[i][2])

        answer = 0

        for start, end, value in events:
            next_index = bisect_right(start_times, end)

            total = value

            if next_index < n:
                total += suffix_max[next_index]

            answer = max(answer, total)

        return answer

solution = Solution()

# Provided examples
assert solution.maxTwoEvents([[1,3,2],[4,5,2],[2,4,3]]) == 4  # choose two non-overlapping events
assert solution.maxTwoEvents([[1,3,2],[4,5,2],[1,5,5]]) == 5  # single event is optimal
assert solution.maxTwoEvents([[1,5,3],[1,5,1],[6,6,5]]) == 8  # choose first and third

# Two events overlap at boundary
assert solution.maxTwoEvents([[1,2,4],[2,3,5]]) == 5  # cannot attend both because intervals are inclusive

# Completely non-overlapping events
assert solution.maxTwoEvents([[1,2,4],[3,4,5]]) == 9  # take both

# Multiple identical intervals
assert solution.maxTwoEvents([[1,5,1],[1,5,2],[1,5,3]]) == 3  # only one can be taken

# Best answer uses only one event
assert solution.maxTwoEvents([[1,10,100],[2,3,5],[4,5,6]]) == 100  # single large event

# Large value near limits
assert solution.maxTwoEvents([[1,1,1000000],[2,2,1000000]]) == 2000000  # max values

# Events already sorted
assert solution.maxTwoEvents([[1,2,1],[3,4,2],[5,6,3]]) == 5  # choose best two

# Events not sorted
assert solution.maxTwoEvents([[5,6,3],[1,2,1],[3,4,2]]) == 5  # sorting required

# Minimum input size
assert solution.maxTwoEvents([[1,2,3],[4,5,6]]) == 9  # exactly two events

Test Summary

Test Why
[[1,3,2],[4,5,2],[2,4,3]] Standard overlapping and non-overlapping mix
[[1,3,2],[4,5,2],[1,5,5]] Best answer uses one event
[[1,5,3],[1,5,1],[6,6,5]] Combines distant compatible events
[[1,2,4],[2,3,5]] Validates inclusive interval rule
[[1,2,4],[3,4,5]] Simple non-overlapping pair
[[1,5,1],[1,5,2],[1,5,3]] All events overlap
[[1,10,100],[2,3,5],[4,5,6]] Large single event dominates
[[1,1,1000000],[2,2,1000000]] Large values and tiny intervals
Already sorted input Confirms algorithm works on sorted data
Unsorted input Confirms sorting step is necessary
Minimum size input Validates smallest constraint

Edge Cases

Events Touching at Boundaries

A very common source of bugs is misunderstanding the inclusive interval rule.

For example:

[1,2] and [2,3]

These events overlap because one ends exactly when the other starts.

A naive implementation might incorrectly allow both events. Our solution avoids this by searching for:

start_time > current_end

instead of:

start_time >= current_end

Using bisect_right correctly enforces this rule.

Best Solution Uses Only One Event

The problem allows choosing at most two events, not exactly two.

Consider:

[[1,10,100],[2,3,5],[4,5,6]]

The optimal answer is 100, using only the first event.

Our implementation naturally handles this because every event is evaluated individually before optionally adding a second compatible event.

All Events Overlap

If every event overlaps with every other event, then no pair can be selected.

Example:

[[1,5,1],[1,5,2],[1,5,3]]

The correct answer is simply the maximum single event value.

The binary search will fail to find compatible future events, so the algorithm correctly falls back to considering single events only.