Is Two Best Non-Overlapping Events easy or hard?

Two Best Non-Overlapping Events is typically rated Medium difficulty. The challenge comes from recognizing that sorting and binary search allow efficient pairing of events without checking every combination.

How to solve Two Best Non-Overlapping Events in O(n)?

Pure O(n) is generally not achievable because the events must be sorted by start time or end time to efficiently detect non-overlapping intervals. After sorting, the remaining processing can be linear with auxiliary arrays, but the sorting step keeps the total complexity at O(n log n).

What is the best approach for Two Best Non-Overlapping Events?

The most efficient approach sorts events by start time and uses binary search to locate the next event that begins after the current one ends. A suffix maximum array tracks the best value obtainable from later events. This reduces the search for the second event from O(n) to O(log n), resulting in O(n log n) total time.

What data structure is used in Two Best Non-Overlapping Events?

The solution primarily uses arrays along with sorting and binary search. Many implementations also maintain a suffix maximum array to quickly retrieve the best value among future events. Some variations use heaps (priority queues), but binary search over sorted events is the most common technique.

What is the time complexity of Two Best Non-Overlapping Events?

The optimal solution runs in O(n log n) time. Sorting the events requires O(n log n), and each event performs a binary search to find the next non-overlapping event in O(log n). Space complexity is O(n) for storing suffix maximum values or dynamic programming states.

Two Best Non-Overlapping Events Python or Java solution approach?

In Python or Java, sort the events by start time and build a suffix maximum array of event values. For each event, perform a binary search to find the first event whose start time is greater than the current event's end time, then combine their values to update the maximum result. The overall complexity remains O(n log n).

Is Two Best Non-Overlapping Events asked at Google, Amazon, or Meta?

Interval scheduling and event selection problems frequently appear in interviews at companies like Amazon, Google, and Meta. Variations involving overlapping intervals, scheduling optimization, and maximum profit selection are common. This problem tests sorting, binary search, and dynamic programming skills.

Description Hints 2 Solution Video 22:27

2054. Two Best Non-Overlapping Events

Medium64.0% acceptance7 companies

You are given a 0-indexed 2D integer array of events where events[i] = [startTime_i, endTime_i, value_i]. The i^th event starts at startTime_iand ends at endTime_i, and if you attend this event, you will receive a value of value_i. 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.

Example 1:

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:

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

Example 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.

Constraints:

2 <= events.length <= 10⁵
events[i].length == 3
1 <= startTime_i <= endTime_i <= 10⁹
1 <= value_i <= 10⁶

Asked at 7 companies

Grammarly Razorpay JPMorgan Chase

Google Amazon Microsoft Meta

Topics

Hints open one at a time

Hint 1

How can sorting the events on the basis of their start times help? How about end times?

Hint 2

How can we quickly get the maximum score of an interval not intersecting with the interval we chose?

22:27

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution