停车困境(Parking Dilemma)问题描述样例注意事项代码

124 阅读 0 评论 82 点赞

我是靠谱客的博主孤独手机，这篇文章主要介绍停车困境(Parking Dilemma)问题描述样例注意事项代码，现在分享给大家，希望可以做个参考。

问题描述

停车场里停着许多汽车。停车位是一条很长的直线，每米都有一个停车位。当前很多汽车停放，您想通过建造屋顶来遮雨挡雨。要求至少有k辆车的车顶被车顶遮盖，要覆盖k辆车的车顶的最小长度是多少？
该函数具有以下参数：

cars：长度的整数数组，表示停放汽车的停车位
k：整数，表示必须被车顶遮盖的汽车数量

样例

示例:
输入:
cars: [2, 10, 8, 17]
k: 3
输出: 9
解释：您可以建立长度为9的屋顶，覆盖从第2个到第10个的所有停车位，因此在第2、10、8个位置覆盖3辆车，没有较短的可以覆盖3辆车的车顶，所以答案是 9

注意事项

1 <= n <= 10^5
1 <= k <= n
0 <= cars[i] <= 10^14
所有车位上面的车都是唯一的

代码

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
import java.util.Arrays;
public class Parking_Dilemma {
/**
* @param cars:
integer array of length denoting the parking slots where cars are parked
* @param k: integer denoting the number of cars that have to be covered by the roof
* @return: return the minium length of the roof that would cover k cars
*/
public int ParkingDilemma(int[] cars, int k) {
// write your code here
Arrays.sort(cars);
int len = cars.length;
int min = cars[k-1] - cars[0];
for (int i = 1; i <= len - k; i++) {
if (min > cars[k-1+i] - cars[i]) {
min = cars[k-1+i] - cars[i];
}
}
return min;
}
}