【算法】区间调度算法 £神魔★判官ぃ 2024-02-18 13:23 21阅读 0赞 #### 目录 #### * 1.概述 * 2.代码实现 * 3.应用 ## 1.概述 ## (1)区间调度算法 (Interval Scheduling Algorithm) 是一种**在给定的一组任务中,选择尽可能多的相互不冲突的任务的算法**。在这个问题中,每个任务都有一个开始时间和结束时间。两个任务是相互冲突的,当且仅当它们的时间段有重叠部分。目标是选择最大数量的任务,使得它们不相互冲突。 (2)该问题可以用贪心算法解决,其基本思想是按照任务结束时间的顺序,依次选择结束时间最早的任务,并且保证该任务与之前已选任务不冲突。具体实现步骤如下: * ① 将任务按照结束时间从早到晚排序; * ② 选择结束时间最早的任务,并将其加入最终结果集合中; * ③ 对于剩余任务中与已选任务不冲突的任务,重复步骤 ②,直到没有剩余任务为止。 (3)下面是一个示例: * 假设有 5 个任务:(1,3), (2,5), (4,7), (6,9), (8,10),其中每个任务用一对时间表示其起始时间和结束时间。 * 按照结束时间从早到晚的顺序,它们的排序结果为:(1,3), (2,5), (4,7), (6,9), (8,10)。 * 根据上述贪心算法,首先选择结束时间最早的任务 (1,3),然后排除掉与该任务冲突的任务 (2,5),接着选择结束时间最早的任务 (4,7),再排除掉与该任务冲突的任务 (6,9),最后选择结束时间最早的任务 (8,10),得到的最终结果集合为 \{(1,3), (4,7), (8,10)\}。 > 区间调度算法的时间复杂度为 `O(nlogn)`,其中 n 是任务数量,主要来自于对任务按照结束时间进行排序。 ## 2.代码实现 ## (1)区间调度算法的代码实现如下: class Solution { public List<int[]> schedule(int[][] intervals) { //将所有区间按照其右端点的值进行升序排序 Arrays.sort(intervals, Comparator.comparingInt(a -> a[1])); //存放选择的区间 List<int[]> selected = new ArrayList<>(); selected.add(intervals[0]); int end = intervals[0][1]; for (int[] interval : intervals) { if (end < interval[0]) { //找到一个与当前区间不相交的区间 selected.add(interval); //更新 end end = interval[1]; } } return selected; } } (2)测试代码如下: class Test { public static void main(String[] args) { int[][] intervals = { { 1, 4}, { 2, 3}, { 3, 6}, { 5, 7}, { 6, 8}, { 8, 10}}; Solution solution = new Solution(); List<int[]> selected = solution.schedule(intervals); for (int[] interval : selected) { System.out.println(Arrays.toString(interval)); } } } 输出结果如下: [2, 3] [5, 7] [8, 10] ## 3.应用 ## (1)区间调度算法的应用场景包括: * **会议安排问题**:有多个会议需要在同一天内安排,但每个会议的时间可能重叠。现在需要找到一种方案,使得尽可能多的会议都可以被安排,并且每个时间段只能安排一场会议。 * **老师安排课程表问题**:有多位老师需要在同一时间段上课,但每位老师的课程可能存在时间上的重叠。现在需要找到一种方案,使得尽可能多的老师都可以安排课程,并且每个时间段只能安排一位老师的课程。 * **医生安排手术问题**:医院有多名医生需要在同一时间段进行手术,但每名医生手术的时间可能存在重叠。现在需要找到一种方案,使得尽可能多的医生都可以进行手术,并且每个时间段只能安排一名医生的手术。 > 以上仅是应用场景的一部分,区间调度算法还可以应用于其他需要优化时间资源利用的问题。 (2)大家可以去 LeetCode 上找相关的区间调度算法的题目来练习,或者也可以直接查看 [LeetCode 算法刷题目录 (Java)][LeetCode _ _Java] 这篇文章中的区间问题章节。如果大家发现文章中的错误之处,可在评论区中指出。 [LeetCode _ _Java]: https://blog.csdn.net/weixin_43004044/article/details/122477673
相关 【算法】区间调度算法 目录 1.概述 2.代码实现 3.应用 1.概述 (1)区间调度算法 (Interval Scheduling Algorithm) 是一种在给 £神魔★判官ぃ/ 2024年02月18日 13:23/ 0 赞/ 22 阅读
相关 调度算法详解 调度算法详解 适合早期批处理系统的算法 先来先服务(FCFS, First Come First Serve) 短作业优先( SJF, S た 入场券/ 2023年10月05日 13:43/ 0 赞/ 47 阅读
相关 区间合并算法 EXCEL 区间值怎么算? =VLOOKUP(A1,\{0,2;1.01,2.8;1.51,3.3;2.01,3.8;2.51,4\},2) 如图所示: 更多追问追答 落日映苍穹つ/ 2023年09月25日 08:53/ 0 赞/ 55 阅读
相关 区间合并算法 算法:st,ed表示当前区间的左端点和右端点 1.将所有区间按左端点排序 2.扫描整个区间,扫描的过程中,将所有可能有交集的区间合并 (1)a区间在当前区间的内部:st和 港控/mmm°/ 2022年10月27日 01:40/ 0 赞/ 152 阅读
相关 进程调度算法 调度算法是指:根据系统的资源分配策略所规定的资源分配算法。 1. 先来先服务 1. 先来先服务调度算法。先来先服务(FCFS)调度算法是一种最简单的调度算法, ゝ一世哀愁。/ 2022年08月25日 00:27/ 0 赞/ 328 阅读
相关 磁盘调度算法 磁盘调度在多道程序设计的计算机系统中,各个进程可能会不断提出不同的对磁盘进行读/写操作的请求。由于有时候这些进程的发送请求的速度比磁盘响应的还要快,因此我们有必要为每个磁盘设备 女爷i/ 2022年07月16日 00:45/ 0 赞/ 190 阅读
相关 进程调度算法 一、先来先服务和短作业(进程)优先调度算法 1.先来先服务调度算法 先来先服务(FCFS)调度算法是一种最简单的调度算法,该算法既可用于作业调度,也可用于进程调度。当在 我就是我/ 2022年07月14日 22:20/ 0 赞/ 273 阅读
相关 调度算法小结 处理机管理的工作是对CPU进行合理的分配使用,以提高处理机利用率,并使各用户公平地得到处理机资源。 CPU可分配的资源是在处理器上的执行时间,分配的途径是调度。 悠悠/ 2022年06月13日 14:38/ 0 赞/ 314 阅读
相关 磁盘调度算法 需求分析 分别实现先到先服务调度(FCFS)磁盘调度算法、最短寻道时间优先算法(SSTF)、“电梯”调度算法(SCAN算法)、C-SCAN算法、LOOK调度算法和C-LO 川长思鸟来/ 2022年02月03日 02:49/ 0 赞/ 345 阅读
相关 进程调度算法 需求分析 分别实现先到先服务调度(FCFS)、最短作业优先调度(SJF)、高响应比优先调度、(抢占式)优先权调度和时间片轮转调度五种进程调度算法。 概要设计 1. 待我称王封你为后i/ 2022年02月03日 02:41/ 0 赞/ 334 阅读
还没有评论,来说两句吧...