LintCode题解 | IBM OA真题：停车困境

【题目描述】
停车场里停着许多汽车。 停车位是一条很长的直线，每米都有一个停车位。 当前很多汽车停放，您想通过建造屋顶来遮雨挡雨。 要求至少有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

【评测与题解】

→戳这里在线评测及查看题解

/**
* 本参考程序来自九章算法，由 @C同学 提供。版权所有，转发请注明出处。
* - 九章算法致力于帮助更多中国人找到好的工作，教师团队均来自硅谷和国内的一线大公司在职工程师。
* - 现有的面试培训课程包括：九章算法班，系统设计班，算法强化班，Java入门与基础算法班，Android 项目实战班，
* - Big Data 项目实战班，算法面试高频题班, 动态规划专题班
* - 更多详情请见官方网站：http://www.jiuzhang.com/?source=code
*/ 

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 min = Integer.MAX_VALUE;
        for(int i=0;i+k-1<cars.length; i++) min = Math.min(min,(cars[i+k-1]-cars[i]+1));
        return min;
    }
}