Maximum Number of Events That Can Be Attended II

arraybinary searchdynamic programming

Problem Statement

You are given an array of events where events[i] = [startDay _i , endDay _i , value _i ] . The i ^th event starts at startDay _i _ and ends at endDay _i , and if you attend this event, you will receive a value of value _i . You are also given an integer k which represents the maximum number of events you can attend.

You can only attend one event at a time. If you choose to attend an event, you must attend the entire event. Note that the end day is inclusive : that is, you cannot attend two events where one of them starts and the other ends on the same day.

Return the maximum sum of values that you can receive by attending events.

Examples

Example 1

Input: events = [[1,2,4],[3,4,3],[2,3,1]], k = 2
Output: 7
Choose the green events, 0 and 1 (0-indexed) for a total value of 4 + 3 = 7.

Example 2

Input: events = [[1,2,4],[3,4,3],[2,3,10]], k = 2
Output: 10
Choose event 2 for a total value of 10.
Notice that you cannot attend any other event as they overlap, and that you do not have to attend k events.

Example 3

Input: events = [[1,1,1],[2,2,2],[3,3,3],[4,4,4]], k = 3
Output: 9
Although the events do not overlap, you can only attend 3 events. Pick the highest valued three.

Constraints

1 <= k <= events.length

1 <= k * events.length <= 10 ^6

1 <= startDay _i <= endDay _i <= 10 ^9

1 <= value _i <= 10 ^6

😤

Hard

Difficulty

Topic Info

ModuleDSA

CategoryArray

Sub-topicBinary Search