原文链接: https://leetcode-cn.com/problems/two-best-non-overlapping-events

英文原文

You are given a 0-indexed 2D integer array of events where events[i] = [startTimei, endTimei, valuei]. The ith event starts at startTimei and ends at endTimei, and if you attend this event, you will receive a value of valuei. 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 <= 105
• events[i].length == 3
• 1 <= startTimei <= endTimei <= 109
• 1 <= valuei <= 106

中文题目

给你一个下标从 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：

输入：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

通过代码

高赞题解

由于至多可以选两个活动，我们可以对活动排序，枚举其中一个活动的价值并求出其余不重叠活动的最大价值，二者相加的最大值即为答案。为了方便统计另一个活动的最大价值，我们可以对活动排序，有两种排序策略：

• 按开始时间排序
• 按结束时间排序

如果按开始时间排序，那么对于一个活动而言，结束时间小于该活动开始时间的活动必然不会与该活动重叠，因此我们可以用一个优先队列（小根堆）存储活动的结束时间和价值，这样就能在遍历活动的同时，不断从堆顶弹出小于当前活动开始时间的活动，并维护这些活动的最大价值。

如果按结束时间排序，如果是从前往后扫描活动，对于每个活动，我们需要知道小于该活动开始时间的所有活动的最大价值。但是开始时间不是有序的，最大价值不好维护。如果是从后往前扫描活动就可以做，做法同上，用大根堆存储活动的开始时间和价值。

下面代码采用按开始时间排序的写法。

func maxTwoEvents(events [][]int) (ans int) {
	sort.Slice(events, func(i, j int) bool { return events[i][0] < events[j][0] }) // 按开始时间排序
	h := hp{}
	maxVal := 0
	for _, e := range events {
		start, end, val := e[0], e[1], e[2]
		for len(h) > 0 && h[0].end < start { // 如果结束时间早于当前活动开始时间
			maxVal = max(maxVal, heap.Pop(&h).(pair).val) // 更新前面可以选择的活动的最大价值
		}
		ans = max(ans, maxVal+val) // 至多参加两个活动
		heap.Push(&h, pair{end, val})
	}
	return
}

type pair struct{ end, val int }
type hp []pair
func (h hp) Len() int            { return len(h) }
func (h hp) Less(i, j int) bool  { return h[i].end < h[j].end }
func (h hp) Swap(i, j int)       { h[i], h[j] = h[j], h[i] }
func (h *hp) Push(v interface{}) { *h = append(*h, v.(pair)) }
func (h *hp) Pop() interface{}   { a := *h; v := a[len(a)-1]; *h = a[:len(a)-1]; return v }

func max(a, b int) int {
	if b > a {
		return b
	}
	return a
}

统计信息

通过次数	提交次数	AC比率
2420	7369	32.8%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言