DEV Community
·
2054. 两个最佳不重叠事件
💡
原文英文，约700词，阅读约需3分钟。
📝
内容提要
给定一个二维数组events，表示事件的开始时间、结束时间和价值。选择最多两个不重叠的事件，使其价值和最大。可以通过按结束时间排序和二分查找高效找到不重叠事件并计算最大和。
🎯
关键要点
- 给定一个二维数组events，表示事件的开始时间、结束时间和价值。
- 选择最多两个不重叠的事件，使其价值和最大。
- 事件的开始时间和结束时间是包含的，不能选择同时开始或结束的事件。
- 通过按结束时间排序，可以高效找到不重叠的事件。
- 使用二分查找找到在当前事件开始时间之前结束的最新事件。
- 动态规划中维护到当前事件的最大价值，以便快速计算两个事件的最大和。
- 对于每个事件，计算可能的和，包括当前事件和最佳不重叠事件的和。
- 排序的复杂度为O(n log n)，每个事件的二分查找复杂度为O(log n)，整体复杂度为O(n log n)。
➡️
