企业官网建设流程全解析

外贸网站建设网站开发,产品代理网,网络营销理论有哪些,天津网站建设哪家做得好适合人群#xff1a;有一定算法基础#xff0c;想深入理解区间调度 动态规划的程序员 难度#xff1a;中等 核心知识点#xff1a;排序、动态规划、二分查找、前缀最大值优化 #x1f3af; 问题描述 给你一个二维数组 events#xff0c;其中 events[i] [startTime, en…适合人群有一定算法基础想深入理解区间调度 动态规划的程序员难度中等核心知识点排序、动态规划、二分查找、前缀最大值优化 问题描述给你一个二维数组events其中events[i] [startTime, endTime, value]。第 i 个活动开始于startTime[i]结束于endTime[i]如果你参加这个活动可以获得价值value[i]你最多可以参加 2 个不重叠的活动求最大价值不重叠定义如果活动 A 结束于时间 t那么活动 B 必须在t1或之后开始。 示例示例 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 思路分析第一反应背包问题很多人包括我第一眼会想到0-1 背包物品 活动重量 时间跨度价值 value容量 总时间范围但这是错的❌原因背包问题的约束是总重量不超过容量这道题的约束是时间不能重叠时间重叠 ≠ 重量累加举个反例活动 A: [1, 5, 100] (时间跨度 4) 活动 B: [2, 3, 50] (时间跨度 1)如果用背包思路A 和 B 的总重量是 5看起来可以装下。但实际上它们时间重叠不能同时选正确思路区间调度问题这是一个区间调度问题的变种经典的区间调度选尽可能多的不重叠活动贪心这道题最多选 2 个求最大价值动态规划 解法一暴力枚举O(n²)核心思想既然最多选 2 个那就穷举所有可能的活动对只选 1 个活动 i → 价值 value[i]选 2 个活动 (i, j) → 如果不冲突价值 value[i] value[j]代码实现defmaxTwoEvents(events):nlen(events)max_value0# 1. 只选一个活动foriinrange(n):max_valuemax(max_value,events[i][2])# 2. 选两个活动foriinrange(n):forjinrange(i1,n):# 判断是否不重叠ifevents[i][1]events[j][0]orevents[j][1]events[i][0]:max_valuemax(max_value,events[i][2]events[j][2])returnmax_value复杂度分析时间复杂度O(n²)空间复杂度O(1)能否通过对于 n ≤ 1000可以通过对于 n ≤ 10⁵LeetCode 的数据范围会超时❌ 解法二排序 动态规划 二分查找O(n log n)核心思想1️⃣ 先排序按endTime升序排序这样处理到活动 i 时前面所有活动的结束时间都 ≤events[i][1]方便用二分查找找到最后一个不冲突的活动2️⃣ 动态规划状态定义dp[i] 选择第 i 个活动时能获得的最大价值状态转移情况 1只选活动 i →dp[i] value[i]情况 2选活动 i 前面某个不冲突的活动 j →dp[i] value[i] dp[j]其中j 是满足events[j].endTime events[i].startTime的最后一个活动。3️⃣ 二分查找优化用二分查找快速找到 j 的位置defbinary_search(events,i):找到最后一个 endTime events[i].startTime 的活动left,right0,i-1result-1whileleftright:mid(leftright)//2ifevents[mid][1]events[i][0]:resultmid leftmid1else:rightmid-1returnresult4️⃣ 前缀最大值优化如果直接用dp[i] value[i] max(dp[0:j])每次需要 O(n) 扫描。优化维护一个max_dp[i]表示前 i 个活动中 dp 的最大值max_dp[i]max(max_dp[i-1],dp[i])这样查询变成 O(1)完整代码defmaxTwoEvents(events):# 1. 按结束时间排序events.sort(keylambdax:x[1])nlen(events)# 2. 初始化 DPdp[0]*n# dp[i] 选第 i 个活动的最大价值max_dp[0]*n# max_dp[i] 前 i 个活动中 dp 的最大值# 3. 动态规划foriinrange(n):# 情况 1只选活动 idp[i]events[i][2]# 情况 2选活动 i 前面某个不冲突的活动jbinary_search(events,i)ifj!-1:dp[i]max(dp[i],events[i][2]max_dp[j])# 更新前缀最大值max_dp[i]max(max_dp[i-1]ifi0else0,dp[i])# 4. 返回最大值returnmax_dp[n-1]defbinary_search(events,i):找到最后一个 endTime events[i].startTime 的活动left,right0,i-1result-1whileleftright:mid(leftright)//2ifevents[mid][1]events[i][0]:resultmid leftmid1else:rightmid-1returnresult复杂度分析操作时间复杂度排序O(n log n)遍历每个活动O(n)每次二分查找O(log n)总计O(n log n)空间复杂度O(n)dp 和 max_dp 数组 算法流程图输入: events [[1,3,2],[4,5,2],[2,4,3]] ↓ 排序 (按 endTime 升序) ↓ events [[1,3,2],[2,4,3],[4,5,2]] ↓ 遍历每个活动 i: - 只选 i: dp[i] value[i] - 二分查找: 找最后一个不冲突的 j - 选 ij: dp[i] value[i] max_dp[j] - 更新: max_dp[i] max(max_dp[i-1], dp[i]) ↓ 返回 max_dp[n-1] 时间轴可视化示例: events [[1,3,2],[4,5,2],[2,4,3]] 排序后: 活动 0: [1----3] value2 活动 1: [2---4] value3 活动 2: [4----5] value2 时间轴: 0 1 2 3 4 5 6 [--0--] [-1--] [--2--] DP 过程: i0: dp[0]2, max_dp[0]2 (只选活动0) i1: dp[1]3, max_dp[1]3 (只选活动1价值更高) i2: - 只选2: dp[2]2 - 选02: events[0].endTime3 events[2].startTime4 ✅ dp[2] 2 max_dp[0] 2 2 4 - max_dp[2] max(3, 4) 4 答案: 4 关键技巧总结1. 为什么按 endTime 排序处理活动 i 时前面所有活动都已结束方便用二分查找找到最后一个不冲突的活动符合从前往后的 DP 思路2. 二分查找的边界# 我们要找最后一个满足 events[j].endTime events[i].startTime 的 j# 即events[j][1] events[i][0]# 标准的 lower_bound 变体ifevents[mid][1]events[i][0]:resultmid leftmid1# 继续往右找看有没有更大的else:rightmid-13. 前缀最大值的妙用不用每次 O(n) 扫描max(dp[0:j])维护max_dp[i] max(max_dp[i-1], dp[i])查询变成 O(1) 测试用例# 测试 1基础情况events[[1,3,2],[4,5,2],[2,4,3]]assertmaxTwoEvents(events)4# 测试 2只选一个更优events[[1,3,2],[4,5,2],[1,5,5]]assertmaxTwoEvents(events)5# 测试 3两个不相邻events[[1,5,3],[1,5,1],[6,6,5]]assertmaxTwoEvents(events)8# 测试 4全部重叠events[[1,5,10],[2,4,20],[3,6,15]]assertmaxTwoEvents(events)20# 测试 5全部不重叠events[[1,2,1],[3,4,2],[5,6,3]]assertmaxTwoEvents(events)5# 选后两个 扩展思考如果改成最多选 k 个活动状态定义dp[i][k] 前 i 个活动中选恰好 k 个的最大价值时间复杂度O(n² · k)可能需要线段树优化如果活动价值可以叠加多次变成加权区间调度问题Weighted Interval Scheduling经典 DP 问题贪心不再适用 相关题目LeetCode 435. 无重叠区间贪心LeetCode 452. 用最少数量的箭引爆气球贪心LeetCode 1235. 规划兼职工作本题的 k∞ 版本 总结方法时间复杂度空间复杂度适用范围暴力枚举O(n²)O(1)n ≤ 1000DP 二分 前缀优化O(n log n)O(n)n ≤ 10⁵ ✅核心思想排序减少搜索空间动态规划避免重复计算二分查找加速查询前缀最大值优化状态转移程序员视角排序 预处理让数据变得有序可查DP 缓存避免重复计算二分 索引优化把 O(n) 查询降到 O(log n)前缀最大值 空间换时间类似数据库的物化视图 写在最后这道题是一个很好的算法组合拳练习不是单纯的贪心或 DP需要排序 DP 二分 前缀优化四个技巧配合体现了分而治之的思想如果你能独立写出这道题说明你已经具备了✅ 问题抽象能力识别出这是区间调度问题✅ 算法设计能力选择合适的数据结构和算法✅ 优化思维从 O(n²) 优化到 O(n log n)继续加油如果这篇文章对你有帮助欢迎点赞、收藏、分享有问题欢迎在评论区讨论