2054-两个最好的不重叠活动

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:25 2023-09-13 16:06:25 Updated    

给你一个下标从 0 开始的二维整数数组 events ，其中 events[i] = [startTimei, endTimei, valuei] 。第 i 个活动开始于 startTimei ，结束于 endTimei ，如果你参加这个活动，那么你可以得到价值
valuei 。你 最多 可以参加 两个时间不重叠 活动，使得它们的价值之和 最大 。

请你返回价值之和的 最大值 。

注意，活动的开始时间和结束时间是 包括
在活动时间内的，也就是说，你不能参加两个活动且它们之一的开始时间等于另一个活动的结束时间。更具体的，如果你参加一个活动，且结束时间为 t
，那么下一个活动必须在 t + 1 或之后的时间开始。

示例 1:

**输入：** events = [[1,3,2],[4,5,2],[2,4,3]]
**输出：** 4
**解释：** 选择绿色的活动 0 和 1 ，价值之和为 2 + 2 = 4 。

示例 2：

Example 1 Diagram

**输入：** events = [[1,3,2],[4,5,2],[1,5,5]]
**输出：** 5
**解释：** 选择活动 2 ，价值和为 5 。

示例 3：

**输入：** events = [[1,5,3],[1,5,1],[6,6,5]]
**输出：** 8
**解释：** 选择活动 0 和 2 ，价值之和为 3 + 5 = 8 。

提示：

  • 2 <= events.length <= 105
  • events[i].length == 3
  • 1 <= startTimei <= endTimei <= 109
  • 1 <= valuei <= 106

方法一：时间戳排序

思路与算法

我们可以将所有活动的左右边界放在一起进行自定义排序。具体地，我们用 (\textit{ts}, \textit{op}, \textit{val}) 表示一个「事件」：

  • op 表示该事件的类型。如果 op} = 0，说明该事件表示一个活动的开始；如果 op} = 1，说明该事件表示一个活动的结束。

  • ts 表示该事件发生的时间，即活动的开始时间或结束时间。

  • val 表示该事件的价值，即对应活动的 value 值。

我们将所有的时间按照 ts 为第一关键字升序排序，这样我们就能按照时间顺序依次处理每一个事件。当 ts 相等时，我们按照 op 为第二关键字升序排序，这是因为题目中要求了「第一个活动的结束时间不能等于第二个活动的起始时间」，因此当时间相同时，我们先处理开始的事件，再处理结束的事件。

当排序完成后，我们就可以通过对所有的事件进行一次遍历，从而算出最多两个时间不重叠的活动的最大价值：

  • 当我们遍历到一个结束事件时，我们用 val 来更新 bestFirst，其中 bestFirst 表示当前已经结束的所有活动的最大价值。这样做的意义在于，所有已经结束的事件都可以当作第一个活动。

  • 当我们遍历到一个开始事件时，我们将该活动当作第二个活动，由于第一个活动的最大价值为 bestFirst，因此我们用 val} + \textit{bestFirst 更新答案即可。

代码

[sol1-C++]
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
30
31
32
33
34
struct Event {
    // 时间戳
    int ts;
    // op = 0 表示左边界，op = 1 表示右边界
    int op;
    int val;
    Event(int _ts, int _op, int _val): ts(_ts), op(_op), val(_val) {}
    bool operator< (const Event& that) const {
        return tie(ts, op) < tie(that.ts, that.op);
    }
};

class Solution {
public:
    int maxTwoEvents(vector<vector<int>>& events) {
        vector<Event> evs;
        for (const auto& event: events) {
            evs.emplace_back(event[0], 0, event[2]);
            evs.emplace_back(event[1], 1, event[2]);
        }
        sort(evs.begin(), evs.end());
        
        int ans = 0, bestFirst = 0;
        for (const auto& [ts, op, val]: evs) {
            if (op == 0) {
                ans = max(ans, val + bestFirst);
            }
            else {
                bestFirst = max(bestFirst, val);
            }
        }
        return ans;
    }
};
[sol1-Python3]
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
class Event:
    def __init__(self, ts: int, op: int, val: int):
        self.ts = ts
        self.op = op
        self.val = val
    
    def __lt__(self, other: "Event") -> bool:
        return (self.ts, self.op) < (other.ts, other.op)


class Solution:
    def maxTwoEvents(self, events: List[List[int]]) -> int:
        evs = list()
        for event in events:
            evs.append(Event(event[0], 0, event[2]))
            evs.append(Event(event[1], 1, event[2]))
        evs.sort()

        ans = bestFirst = 0
        for ev in evs:
            if ev.op == 0:
                ans = max(ans, ev.val + bestFirst)
            else:
                bestFirst = max(bestFirst, ev.val)
        
        return ans

复杂度分析

  • 时间复杂度：O(n \log n)，其中 n 是数组 events 的长度。

  • 空间复杂度：O(n)。

 Comments
On this page
2054-两个最好的不重叠活动