Two Best Non-Overlapping Events

arraybinary searchdynamic programming

Problem Statement

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 _i _ and 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 .

Examples

Example 1

Input: events = [[1,3,2],[4,5,2],[2,4,3]]
Output: 4
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
Choose event 2 for a sum of 5.

Example 3

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

Constraints

2 <= events.length <= 10 ^5

events[i].length == 3

1 <= startTime _i <= endTime _i <= 10 ^9

1 <= value _i <= 10 ^6

🤔

Medium

Difficulty

Topic Info

ModuleDSA

CategoryArray

Sub-topicBinary Search