贪心算法应用：带权任务间隔调度问题详解

article/2025/7/2 1:36:37

在这里插入图片描述

贪心算法应用：带权任务间隔调度问题详解

贪心算法是一种在每一步选择中都采取在当前状态下最好或最优（即最有利）的选择，从而希望导致结果是全局最好或最优的算法。带权任务间隔调度问题是贪心算法的一个经典应用场景。

问题定义

**带权任务间隔调度问题(Weighted Interval Scheduling Problem)**描述如下：

  • 给定一组任务，每个任务有一个开始时间、结束时间和权重（价值）
  • 目标：选择一组互不重叠的任务，使得这些任务的总权重最大

与普通间隔调度问题不同之处在于，这里每个任务有不同的权重，我们需要考虑权重而不仅仅是任务数量。

问题分析

输入表示

每个任务可以表示为三元组 (start, end, weight)：

class Task {int start;int end;int weight;public Task(int start, int end, int weight) {this.start = start;this.end = end;this.weight = weight;}
}

关键概念

  1. 兼容任务：两个任务如果它们的执行时间不重叠，则称为兼容任务
  2. p(j)：对于任务j，p(j)是最大的i < j且任务i与任务j兼容的任务索引

贪心算法解决方案

1. 动态规划解法（非贪心）

首先我们看一下动态规划解法，以便与贪心算法对比：

public int weightedIntervalScheduling(Task[] tasks) {// 按结束时间排序Arrays.sort(tasks, (a, b) -> a.end - b.end);int n = tasks.length;int[] dp = new int[n + 1];for (int j = 1; j <= n; j++) {int i = latestNonOverlapping(tasks, j - 1);int weight = tasks[j - 1].weight;dp[j] = Math.max(weight + (i != -1 ? dp[i + 1] : 0), dp[j - 1]);}return dp[n];
}private int latestNonOverlapping(Task[] tasks, int j) {for (int i = j - 1; i >= 0; i--) {if (tasks[i].end <= tasks[j].start) {return i;}}return -1;
}

这种方法时间复杂度为O(n²)，我们可以用贪心算法优化。

2. 贪心算法优化

贪心算法的关键在于如何选择任务。我们可以通过以下步骤实现：

  1. 将所有任务按照结束时间排序
  2. 使用二分查找快速找到p(j)
  3. 使用记忆化或自底向上的动态规划

优化后的Java实现：

import java.util.Arrays;
import java.util.Comparator;public class WeightedIntervalScheduling {static class Task {int start;int end;int weight;public Task(int start, int end, int weight) {this.start = start;this.end = end;this.weight = weight;}}public static int schedule(Task[] tasks) {// 1. 按结束时间排序Arrays.sort(tasks, Comparator.comparingInt(a -> a.end));int n = tasks.length;int[] dp = new int[n + 1];// 预处理p数组，p[j]表示在任务j之前最后一个不与j冲突的任务索引int[] p = new int[n];for (int j = 0; j < n; j++) {p[j] = binarySearch(tasks, j);}// 动态规划填表dp[0] = 0;for (int j = 1; j <= n; j++) {int include = tasks[j - 1].weight;if (p[j - 1] != -1) {include += dp[p[j - 1] + 1];}dp[j] = Math.max(include, dp[j - 1]);}return dp[n];}// 使用二分查找找到最后一个不与tasks[j]冲突的任务private static int binarySearch(Task[] tasks, int j) {int low = 0;int high = j - 1;int key = tasks[j].start;int result = -1;while (low <= high) {int mid = (low + high) / 2;if (tasks[mid].end <= key) {result = mid;low = mid + 1;} else {high = mid - 1;}}return result;}public static void main(String[] args) {Task[] tasks = {new Task(1, 3, 5),new Task(2, 5, 6),new Task(4, 6, 5),new Task(6, 7, 4),new Task(5, 8, 11),new Task(7, 9, 2)};System.out.println("Maximum weight: " + schedule(tasks));}
}

3. 算法复杂度分析

  1. 排序：O(n log n)
  2. 预处理p数组：n次二分查找，每次O(log n)，总共O(n log n)
  3. 动态规划填表：O(n)

总时间复杂度：O(n log n)，比纯动态规划的O(n²)更高效。

贪心选择性质证明

贪心算法的正确性需要证明其具有贪心选择性质和最优子结构性质。

贪心选择性质：全局最优解可以通过局部最优（贪心）选择达到。

对于带权任务间隔调度问题：

  1. 设任务集按结束时间排序为1, 2, …, n
  2. 设O是最优解，且任务j是O中结束时间最早的任务
  3. 如果任务j不在贪心解中，可以用j替换O中第一个任务，不会降低总权重
  4. 因此存在包含任务j的最优解

最优子结构性质：问题的最优解包含子问题的最优解。

在选择任务j后，剩余问题是求解在j结束后开始的任务集合的最大权重调度，这正是原问题的子问题。

变种与扩展

1. 输出具体任务序列

除了计算最大权重，我们还可以记录具体选择了哪些任务：

public static List<Task> scheduleWithTasks(Task[] tasks) {Arrays.sort(tasks, Comparator.comparingInt(a -> a.end));int n = tasks.length;int[] dp = new int[n + 1];int[] choice = new int[n + 1]; // 记录选择int[] p = new int[n];for (int j = 0; j < n; j++) {p[j] = binarySearch(tasks, j);}dp[0] = 0;for (int j = 1; j <= n; j++) {int include = tasks[j - 1].weight;if (p[j - 1] != -1) {include += dp[p[j - 1] + 1];}if (include > dp[j - 1]) {dp[j] = include;choice[j] = 1; // 选择任务j} else {dp[j] = dp[j - 1];choice[j] = 0; // 不选择任务j}}// 回溯找出选择的任务List<Task> result = new ArrayList<>();int j = n;while (j > 0) {if (choice[j] == 1) {result.add(tasks[j - 1]);j = p[j - 1] + 1; // 跳到前一个兼容任务} else {j--;}}Collections.reverse(result);return result;
}

2. 资源分配扩展

当有多个资源（如多个会议室）时，问题变为区间图着色问题，可以使用贪心算法的最早结束时间策略，配合资源计数来解决。

实际应用场景

带权任务间隔调度算法在实际中有广泛应用：

  1. 会议室安排：选择最有价值的会议组合
  2. 作业调度：CPU任务调度，选择权重最高的任务组合
  3. 广告投放：在有限时间段选择最有价值的广告组合
  4. 课程安排：安排最有价值且不冲突的课程组合

性能优化技巧

  1. 预处理优化：提前计算并存储p(j)数组
  2. 记忆化搜索：使用递归+记忆化代替纯递归
  3. 迭代实现：使用迭代而非递归避免栈溢出
  4. 空间优化：只存储必要的DP状态，减少空间复杂度

与其他算法对比

  1. 与回溯算法对比：

    • 回溯：时间复杂度O(2ⁿ)，可以找到所有解
    • 贪心：时间复杂度O(n log n)，只能找到一种最优解

  2. 与动态规划对比：

    • 动态规划：通常需要填表，可能时间复杂度较高
    • 贪心：利用问题特性优化，通常更高效

  3. 与线性规划对比：

    • 线性规划：更通用但实现复杂
    • 贪心：针对特定问题，实现简单高效

常见错误与陷阱

  1. 排序标准错误：必须按结束时间排序，而不是开始时间或权重
  2. 权重处理不当：不能简单地选择权重最大的任务，需要考虑兼容性
  3. 边界条件处理：注意空任务集和全冲突任务集的特殊情况
  4. 索引处理错误：在实现p(j)时容易出现的off-by-one错误

测试用例设计

好的测试用例应包括：

public class WeightedIntervalSchedulingTest {@Testpublic void testEmptyTasks() {Task[] tasks = {};assertEquals(0, WeightedIntervalScheduling.schedule(tasks));}@Testpublic void testSingleTask() {Task[] tasks = {new Task(1, 3, 5)};assertEquals(5, WeightedIntervalScheduling.schedule(tasks));}@Testpublic void testAllTasksConflict() {Task[] tasks = {new Task(1, 5, 3),new Task(2, 6, 4),new Task(3, 7, 2)};assertEquals(4, WeightedIntervalScheduling.schedule(tasks));}@Testpublic void testNoTasksConflict() {Task[] tasks = {new Task(1, 3, 5),new Task(4, 6, 3),new Task(7, 9, 2)};assertEquals(10, WeightedIntervalScheduling.schedule(tasks));}@Testpublic void testMixedCase() {Task[] tasks = {new Task(1, 3, 5),new Task(2, 5, 6),new Task(4, 6, 5),new Task(6, 7, 4),new Task(5, 8, 11),new Task(7, 9, 2)};assertEquals(16, WeightedIntervalScheduling.schedule(tasks));}
}

总结

带权任务间隔调度问题展示了贪心算法在解决特定类型优化问题时的强大能力。通过合理的问题分析和算法设计，我们可以将看似复杂的O(2ⁿ)问题转化为O(n log n)的高效解决方案。关键在于：

  1. 识别问题的贪心选择性质
  2. 设计合适的排序和选择策略
  3. 结合动态规划避免重复计算
  4. 正确处理边界条件和特殊情况

Java实现时需要注意任务表示、排序、二分查找优化等细节，以确保算法的高效性和正确性。

更多资源：

https://www.kdocs.cn/l/cvk0eoGYucWA

本文发表于【纪元A梦】！


http://www.hkcw.cn/article/XvljxEpnBl.shtml

相关文章

Git-flow流

Git-flow流

Git git是版本控制软件&#xff0c;一般用来做代码版本控制 github是一个免费版本控制仓库是国内外很多开源项目的集中地&#xff0c;其本体是一个git服务器 Git初始化操作 git init 初始化仓库 git status 查看当前仓库的状态 git add . 将改动的文件加到暂存区 gi…
阅读更多...
LeetCode-链表操作题目

LeetCode-链表操作题目

虚拟头指针&#xff0c;在当前head的前面建立一个虚拟头指针&#xff0c;然后哪怕当前的head的val等于提供的val也能进行统一操作 203移除链表元素简单题 /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(…
阅读更多...
mybatisplus的总结

mybatisplus的总结

一.通用Mapper 1.首先创建一个接口与实体类 Data TableName("user") public class User { TableId(value "id", type IdType.AUTO) private Long id; TableField("name") private String name; TableField("age") pri…
阅读更多...
UE5 创建2D角色帧动画学习笔记

UE5 创建2D角色帧动画学习笔记

UE5 创建2D角色帧动画 1.对导入的角色所有帧动画图片Apply paper2d Texture Setting 2.创建图片精灵 Create Sprite 3.全选创建的图片精灵&#xff0c;右键点击 Create Flipbook(创建图像序列视图) 4.双击此paper Flipbook 即可预览该角色帧动画 UE5 2D角色帧动画 Frames P…
阅读更多...
MyBatisPlus--条件构造器及自定义SQL详解

MyBatisPlus--条件构造器及自定义SQL详解

条件构造器 在前面学习快速入门的时候&#xff0c;练习的增删改查都是基于id去执行的&#xff0c;但是在实际开发业务中&#xff0c;增删改查的条件往往是比较复杂的&#xff0c;因此MyBatisPlus就提供了一个条件构造器来帮助构造复杂的条件。 MyBatisPlus支持各种复杂的wher…
阅读更多...
《类和对象--继承》

《类和对象--继承》

引言&#xff1a; 在刚接触C的时候&#xff0c;我们首先学习了有关类和对象的一些基础知识&#xff0c;今天我们就要接着学习类和对象的另一板块–继承。 一&#xff1a;继承的概念和定义 1. 继承的概念 继承(inheritance)机制是面向对象程序设计使代码可以复用的最重要的手…
阅读更多...
利用R语言生成区试中随机区组试验设计——多点

利用R语言生成区试中随机区组试验设计——多点

目前&#xff0c;区试要求对照不得位于区组的首尾小区&#xff0c;且不同区组的相邻小区位置不得出现同一品种。基于这一要求&#xff0c;编写了R语言的随机区组试验设计。此函数可用于多个试验点试验设计生成情况。 rcbd函数有6个参数&#xff1a; local_name为试验点名称的向…
阅读更多...
pytorch基本运算-范数

pytorch基本运算-范数

引言 前序学习进程中&#xff0c;已经对pytorch基本运算有了详细探索&#xff0c;文章链接有&#xff1a; 基本运算 广播失效 乘除法和幂运算 hadamard积、点积和矩阵乘法 上述计算都是以pytorch张量为运算元素&#xff0c;这些张量基本上也集中在一维向量和二维矩阵&#x…
阅读更多...
STM32G4 电机外设篇（四）DAC输出电流波形 + CAN通讯

STM32G4 电机外设篇（四）DAC输出电流波形 + CAN通讯

目录 一、STM32G4 电机外设篇&#xff08;四&#xff09;DAC输出电流波形 CAN通讯1 DAC输出电流波形1.1 STM32CubeMX配置和Keil代码1.2 实验现象 2 CAN/CANFD通讯2.1 STM32CubeMX配置和Keil代码2.2 实验现象 附学习参考网址欢迎大家有问题评论交流 (* ^ ω ^) 一、STM32G4 电机…
阅读更多...
电子电气架构 --- 后轮转向的一点事情

电子电气架构 --- 后轮转向的一点事情

我是穿拖鞋的汉子&#xff0c;魔都中坚持长期主义的汽车电子工程师。 老规矩&#xff0c;分享一段喜欢的文字&#xff0c;避免自己成为高知识低文化的工程师&#xff1a; 做到欲望极简&#xff0c;了解自己的真实欲望&#xff0c;不受外在潮流的影响&#xff0c;不盲从&#x…
阅读更多...
web复习（四）

web复习（四）

盒子模型的例题 例一&#xff1a; <!doctype html> <html> <head> <meta charset"utf-8"> <title>咖啡店banner</title> <style type"text/css"> /*将页面中所有元素的内外边距设置为0*/ *{ padding:0; margin…
阅读更多...
Cesium添加点线面(贴地)

Cesium添加点线面(贴地)

// 创建一个图元集合const primitives viewer.scene.primitives.add(new Cesium.PrimitiveCollection());1、点上图 // 定义点的位置&#xff08;中国不同城市的经纬度&#xff09;const points [{ lon: 116.4074, lat: 39.9042, name: "北京" },{ lon: 121.4737, …
阅读更多...
技术文档：MD520系列变频器配套杭州干扰净GRJ9000S系列EMC电源滤波器安装指南

技术文档：MD520系列变频器配套杭州干扰净GRJ9000S系列EMC电源滤波器安装指南

1. 引言 MD520系列通用变频器是汇川技术有限公司&#xff08;Inovance&#xff09;设计的高性能电流矢量控制交流驱动器&#xff0c;广泛应用于纺织、造纸、机床、包装、食品、风机和水泵等行业。为确保其在复杂电磁环境中稳定运行并不对其他设备造成干扰&#xff0c;手册推荐…
阅读更多...
【基于阿里云搭建数据仓库（离线）】DataWorks中删除节点

【基于阿里云搭建数据仓库（离线）】DataWorks中删除节点

1.右击想要删除的节点&#xff0c;点击删除 2. 显示如下界面&#xff0c;点击“去下线” 3.进入到如下界面&#xff0c;点击红色框出来的 4.重新右击想要删除的目标节点&#xff0c;点击删除 5. 点击去下线 6.点击开始下线 7.点击“确认发布” 8.点击“确认” 9.点击“重新删除…
阅读更多...
【GESP真题解析】第 6 集 GESP 三级 2023 年 9 月编程题 1：小杨的储蓄

【GESP真题解析】第 6 集 GESP 三级 2023 年 9 月编程题 1：小杨的储蓄

大家好，我是莫小特。 这篇文章给大家分享 GESP 三级 2023 年 9 月编程题第 1 题：小杨的储蓄。 题目链接 洛谷链接：B3867 小杨的储蓄 一、完成输入 根据输入格式的描述，输入有两行，第一行为两个整数 N 和 D，数据范围： 1 ≤ N ≤ 1000 1\le N \le 1000 1≤N≤1000， 1 …
阅读更多...
MySQL-多表关系、多表查询

MySQL-多表关系、多表查询

一. 一对多(多对一) 1. 例如&#xff1b;一个部门下有多个员工 在数据库表中多的一方(员工表)、添加字段&#xff0c;来关联一的一方(部门表)的主键 二. 外键约束 1.如将部门表的部门直接删除&#xff0c;然而员工表还存在其部门下的员工&#xff0c;出现了数据的不一致问题&am…
阅读更多...
Arbitrum Stylus 合约实战 ：Rust 实现 ERC721

Arbitrum Stylus 合约实战 ：Rust 实现 ERC721

在上一篇中&#xff0c;我们学习了如何在 stylus 使用 rust 编写 ERC20合约&#xff0c;并且部署到了Arbitrum Sepolia &#xff0c;今天我们继续学习&#xff0c;如何在 stylus 中使用 rust 实现 ERC721 合约&#xff0c;OK, 直接开干&#xff01; 关于环境准备&#xff0c;请…
阅读更多...
超声波测距三大算法实测对比

超声波测距三大算法实测对比

前言 声波测距的数据包含很大噪声&#xff0c;即使障碍物&#xff08;以纸板为例&#xff09;静止&#xff0c;测量距离数据也上下跳变&#xff0c;需要通过数据滤波算法降低测量误差&#xff0c;主要滤波算法有平均值滤波和卡尔曼滤波。 在超声波测距中&#xff0c;无滤波、…
阅读更多...
【2025年5月】AI生产力再探再报：各家智能体持续内卷，前沿应用不断细分

【2025年5月】AI生产力再探再报：各家智能体持续内卷，前沿应用不断细分

前言 2025年5月的个人学习笔记。 一、工具尝鲜快报&#xff1a;初探感觉好玩&#xff0c;但还未深入的工具。 二、生产力军火库&#xff1a;开箱即用的神器&#xff0c;以及一些好用的技巧。 三、前沿动态速递&#xff1a;一些可反复品读的优质资料和个人感兴趣的新工具。 文章…
阅读更多...
ubuntu22.04安装megaton

ubuntu22.04安装megaton

前置 sudo apt-get install git cmake ninja-build generate-ninja安装devkitPro https://blog.csdn.net/qq_39942341/article/details/148388639?spm1001.2014.3001.5502 安装cargo https://blog.csdn.net/qq_39942341/article/details/148387783?spm1001.2014.3001.5501 …
阅读更多...
推荐文章

Copyright @ 2022~2023