2054. Two Best Non-Overlapping Events

Problem

You are given a 0-indexed 2D integer array of events where events[i] = [startTimeᵢ, endTimeᵢ, valueᵢ]. The iᵗʰ event starts at startTimeᵢ and ends at endTimeᵢ, and if you attend this event, you will receive a value of valueᵢ. 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.

https://leetcode.com/problems/two-best-non-overlapping-events/

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ᵢ <= endTimeᵢ <= 10⁹
• 1 <= valueᵢ <= 10⁶

Test Cases

1
2

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

import pytest

from solution import Solution


@pytest.mark.parametrize('events, expected', [
    ([[1,3,2],[4,5,2],[2,4,3]], 4),
    ([[1,3,2],[4,5,2],[1,5,5]], 5),
    ([[1,5,3],[1,5,1],[6,6,5]], 8),

    ([[35,90,47],[72,80,70]], 70),
    ([[10,83,53],[63,87,45],[97,100,32],[51,61,16]], 85),
])
class Test:
    def test_solution(self, events, expected):
        sol = Solution()
        assert sol.maxTwoEvents(events.copy()) == expected

Thoughts

先按 startTime 排序所有 events，逆序遍历一遍可以计算出在每个 startTime 及之后，选一个 event 的最大 value。

再按 endTime 排序，正序遍历一遍计算出在每个 endTime 及之前，选一个 event 的最大 value。

那么对于任意时刻 t，都可以计算出在 t 之前（不含 t）能得到的最大 value，以及在 t 之后（含 t）能得到的最大 value，二者相加就是 t 时刻对应的总的最大 value。

只需要遍历所有 events 的 startTime 和 endTime。因为都已经排序了，对于遍历过程中的每个时刻，可以用常数时间计算其对应的最大 value。

总的时间复杂度 O(n log n)（主要是排序），空间复杂度 O(n)。

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

class Solution:
    def maxTwoEvents(self, events: list[list[int]]) -> int:
        n = len(events)

        events.sort(key=lambda e: e[0])
        max_ge_start = [[e[0], 0] for e in events] # (start time, max value)
        for i in range(-1, -n - 1, -1):
            max_ge_start[i][1] = max(max_ge_start[i+1][1], events[i][2])

        events.sort(key=lambda e: e[1])
        max_le_end = [[e[1], 0] for e in events] # (end time, max value)
        for i in range(n):
            max_le_end[i][1] = max(max_le_end[i-1][1], events[i][2])

        after = best = max_ge_start[0][1]
        before = 0
        i = j = 0
        while j < n:
            if i == n or max_ge_start[i][0] > max_le_end[j][0]:
                before = max_le_end[j][1]
                j += 1
            elif i < n:
                i += 1
                after = max_ge_start[i][1] if i < n else 0

            if after + before > best:
                best = after + before

        return best

不是很快，才 34+%，回头再优化。

许可协议

本文除了题目描述（Problem）部分之外，其他内容由 Calf 原创，采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。

分享文章