华为OD机试 Java 实现【批量处理任务】【2023 B卷 200分】，二分查找

华为OD机试 2023B卷题库疯狂收录中，刷题点这里

专栏导读

本专栏收录于《华为OD机试（JAVA）真题（A卷+B卷）》。

刷的越多，抽中的概率越大，每一题都有详细的答题思路、详细的代码注释、样例测试，发现新题目，随时更新，全天CSDN在线答疑。

一、题目描述

某实验室计算机待处理任务以 [start,end,period] 格式记于二维数组 tasks，表示完成该任务的时间范围为起始时间 start 至结束时间 end 之间，需要计算机投入 period 的时长，注意：

1. period 可为不连续时间
2. 首尾时间均包含在内

处于开机状态的计算机可同时处理任意多个任务，请返回电脑最少开机多久，可处理完所有任务。

二、输入描述

[[1,3,2],[2,5,3],[5,6,2]]

三、输出描述

4

1. tasks[0] 选择时间点 2、3；
2. tasks[1] 选择时间点 2、3、5；
3. tasks[2] 选择时间点 5、6；
4. 因此计算机仅需在时间点 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在线答疑。