贪心算法----区间调度问题
2023-03-14 09:45:04 时间
题目:
有n项工作,每项工作分别在si时间开始,在ti时间结束。对于每项工作,你都可以选择参与与否。如果选择了参与,那么自始至终都必须全程参与。此外,参与工作的时间段不能重复(即使是开始的瞬间和结束的瞬间的重叠也是不允许的)。你的目标是参与尽可能多的工作,那么最多能参与多少项工作呢? 1≤n≤100000 1≤si≤ti≤109。这道题目还可以称作不相交区间问题。
输入:
第一行:n
第二行:n个整数空格隔开,代表n个工作的开始时间
第三行:n个整数空格隔开,代表n个工作的结束时间
样例输入:
5 1 2 4 6 8 3 5 7 9 10
样例输出:
3
说明:选取工作1,3,5。
思路分析:
对于这种区间型问题,最好画一个数轴图来直观的看这个问题。
对这个问题,如果使用贪心算法的话,可能有以下几种考虑:
(1)、每次选取开始时间最早的;
(2)、每次选取结束时间最早的;
(3)、每次选取用时最短的;
(4)、在可选工作中,每次选取与最小可选工作有重叠的部分;
对于上面的四种算法,只有算法(2)是正确的,其它的三种都可以找到相应的反例,举几个例子就很容易发现反例。在编码的过程中要注意一个问题:我们需要对所有的结束时间进行排序,然后选择出没有被这个区间覆盖的而且开始时间大于这个区间的结束时间的下一个区间,其中涉及到了排序但是排完序之后原来的开始时间和结束时间有可能会被打乱,这里用到了Java的面向对象的封装思想。
代码:
import java.util.Arrays; import java.util.Scanner; public class 区间调度问题 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int[] s = new int[n]; int[] t = new int[n]; Job[] jobs = new Job[n]; for (int i = 0; i < n; i++) { s[i] = sc.nextInt(); } for (int i = 0; i < n; i++) { t[i] = sc.nextInt(); } for (int i = 0; i < n; i++) { jobs[i] = new Job(s[i], t[i]); } Arrays.sort(jobs); // 排序这种类型数据必须自定义比较规则 int res = f(n, jobs); System.out.println(res); } private static int f(int n, Job[] jobs) { int cnt = 1; int y = jobs[0].t; for (int i = 0; i < n; i++) { if (jobs[i].s > y) { cnt++; y = jobs[i].t; } } return cnt; } private static class Job implements Comparable<Job> { int s; int t; public Job(int s, int t) { this.s = s; this.t = t; } @Override public int compareTo(Job other) { int x = this.t - other.t; if (x == 0) return this.s - other.s; else return x; } } }
结果:
相关文章
- 在 Go 里用 CGO?这 7 个问题你要关注!
- 9款优秀的去中心化通讯软件 Matrix 的客户端
- 求职数据分析,项目经验该怎么写
- 在OKR中,我看到了数据驱动业务的未来
- 火山引擎云原生大数据在金融行业的实践
- OpenHarmony富设备移植指南(二)—从postmarketOS获取移植资源
- 《数据成熟度指数》报告:64%的企业领袖认为大多数员工“不懂数据”
- OpenHarmony 小型系统兼容性测试指南
- 肯睿中国(Cloudera):2023年企业数字战略三大趋势预测
- 适用于 Linux 的十大命令行游戏
- GNOME 截图工具的新旧截图方式
- System76 即将推出的 COSMIC 桌面正在酝酿大变化
- 2GB 内存 8GB 存储即可流畅运行,Windows 11 极致精简版系统 Tiny11 发布
- 迎接 ecode:一个即将推出的具有全新图形用户界面框架的现代、轻量级代码编辑器
- loongarch架构介绍(三)—地址翻译
- Go 语言怎么解决编译器错误“err is shadowed during return”?
- 敏捷:可能被开发人员遗忘的部分
- Denodo预测2023年数据管理和分析的未来
- 利用数据推动可持续发展
- 在 Vue3 中实现 React 原生 Hooks(useState、useEffect),深入理解 React Hooks 的