阳西网站建设辽宁和生活app下载安装
目录
- 专栏导读
- 一、题目描述
- 二、输入描述
- 三、输出描述
- 四、二分查找
- 五、解题思路
- 六、Java算法源码
- 七、效果展示
- 1、输入
- 2、输出
- 3、说明
华为OD机试 2023B卷题库疯狂收录中，刷题点这里
专栏导读
本专栏收录于《华为OD机试（JAVA）真题（A卷+B卷）》。
刷的越多，抽中的概率越大，每一题都有详细的答题思路、详细的代码注释、样例测试，发现新题目，随时更新，全天CSDN在线答疑。
一、题目描述
某实验室计算机待处理任务以 [start,end,period] 格式记于二维数组 tasks，表示完成该任务的时间范围为起始时间 start 至结束时间 end 之间，需要计算机投入 period 的时长，注意：
- period 可为不连续时间
- 首尾时间均包含在内
处于开机状态的计算机可同时处理任意多个任务，请返回电脑最少开机多久，可处理完所有任务。
二、输入描述
[[1,3,2],[2,5,3],[5,6,2]]
三、输出描述
4
- tasks[0] 选择时间点 2、3；
- tasks[1] 选择时间点 2、3、5；
- tasks[2] 选择时间点 5、6；
- 因此计算机仅需在时间点 2、3、5、6 四个时刻保持开机即可完成任务。
四、二分查找
二分查找（Binary Search），也称为折半查找，是一种在有序数组中查找特定元素的搜索算法。
二分查找的基本思想是将数组分成两部分，确定待查找元素可能存在的那一部分，然后继续对该部分进行二分，直到找到目标元素或者确定该元素不存在于数组中。
比如下面这段Java代码：
public class BinarySearch { public static int binarySearch(int[] array, int target) { int left = 0; int right = array.length - 1; while (left <= right) { int mid = (left + right) / 2; if (array[mid] == target) { return mid; } else if (array[mid] < target) { left = mid + 1; } else { right = mid - 1; } } return -1; } public static void main(String[] args) { int[] array = {1, 3, 5, 7, 9}; int target = 5; int result = binarySearch(array, target); if (result == -1) { System.out.println("Element not found"); } else { System.out.println("Element found at index " + result); } }
}
在这个示例中，binarySearch方法接收一个有序数组array和要查找的目标元素target。然后，使用循环进行二分查找，将搜索范围不断缩小，直到找到目标元素或确定该元素不存在于数组中。如果找到目标元素，返回其索引，否则返回-1。
在main方法中，我们定义一个数组和一个目标元素，然后调用binarySearch方法并打印结果。
五、解题思路
由于每次都是从右到左新增时间点，相当于把若干右侧的区间合并成一个大区间，因此可以用栈来优化。
栈中保存闭区间的左右端点，以及从栈底到栈顶的区间长度之和（类似前缀和）。
合并前先在栈中二分查找左端点所在区间，由于我们保存了长度之和，所以可以算出 [start,end]范围内的运行中的时间点。
如果还需要新增时间点，那么就从右到左合并。
六、Java算法源码
package com.guor.od;import com.alibaba.fastjson.JSON;import java.util.*;
import java.util.function.Predicate;/*** 批量处理任务*/
public class OdTest {public static void main(String[] args) {Scanner sc = new Scanner(System.in);/*** demo：[[2,3,1],[5,5,1],[5,6,2]]* 起始时间，结束时间，需要计算机投入 period 的时长*/int[][] tasks = JSON.parseObject(sc.nextLine(), int[][].class);System.out.println(getPeriod(tasks));}public static int getPeriod(int[][] tasks) {Arrays.sort(tasks, (a, b) -> a[1] - b[1]);// 集合中保存闭区间的左右端点，以及从栈底到栈顶的区间长度之和List<int[]> list = new ArrayList<>();for (int[] task : tasks) {// 起始时间int start = task[0];// 结束时间int end = task[1] + 1;// 需要计算机投入 period 的时长int period = task[2];// 在集合中二分查找左端点所在区间// [[2,3,1],[5,5,1],[5,6,2]]int i = binarySearch(list, (x -> x[1] > start));int max = 0;if (i != list.size()) {int[] arr = list.get(list.size() - 1);max = Math.max(0, arr[2] - list.get(i)[2] + list.get(i)[1] - Math.max(start, list.get(i)[0]));}int temp = Math.max(0, period - max);int cur = end;while (!list.isEmpty() && cur - list.get(list.size() - 1)[1] <= temp) {int[] arr = list.remove(list.size() - 1);temp -= cur - arr[1];cur = arr[0];}list.add(new int[]{cur - temp, end, end - cur + temp + (list.isEmpty() ? 0 : list.get(list.size() - 1)[2])});}return list.get(list.size() - 1)[2];}// 在集合中二分查找左端点所在区间private static int binarySearch(List<int[]> list, Predicate<int[]> predicate) {int left = 0;int right = list.size() - 1;while (left <= right) {int mid = left + (right - left) / 2;if (predicate.test(list.get(mid))) {right = mid - 1;} else {left = mid + 1;}}return left;}
}
七、效果展示
1、输入
[[2,3,1],[5,5,1],[5,6,2]]
2、输出
3
3、说明
- tasks[0] 选择时间点 2 或 3；
- tasks[1] 选择时间点 5；
- tasks[2] 选择时间点 5、6；
- 因此计算机仅需在时间点 2、5、6 或 3、5、6 三个时刻保持开机即可完成任务。
🏆下一篇：华为OD机试真题 Java 实现【路灯照明问题】【2022Q4 100分】，感谢fly晨发现这个问题，并提供更优质的算法
🏆本文收录于，华为OD机试（JAVA）真题（A卷+B卷）
刷的越多，抽中的概率越大，每一题都有详细的答题思路、详细的代码注释、样例测试，发现新题目，随时更新，全天CSDN在线答疑。
