LintCode：1338 · 停车困境

问题描述

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

该函数具有以下参数：
cars：长度的整数数组，表示停放汽车的停车位
k：整数，表示必须被车顶遮盖的汽车数量

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

样例

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

解题思路

1. 停车位是一条很长的直线，也就是说停车位是连续的；我们先对停车位数组cars进行排序；
2. 假设覆盖的第一辆车为数组第i个，那么最后一辆车就是第i+k-1个；我们可以把这看做一个固定的窗口，从头开始向后滑动，找到所求的最小长度。

代码示例(JAVA)

public class Solution {
    /**
     * @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 minSize = cars[cars.length - 1] - cars[0] + 1;
        for(int i = 0; i + k <= cars.length; i++) {
            int size = cars[i + k -1] - cars[i] + 1;
            if (size < minSize) {
                minSize = size;
            }
        }

        return minSize;
    }
}