当前位置: 面试刷题>> 移动车棚 (经典算法题500道)


题目描述补充:

题目:移动车棚

在一个水平直线上,停放着多辆汽车,每辆汽车占据一定的位置区间(即每辆车有一个起始位置和结束位置)。现在需要构建一个可移动的车棚来覆盖这些汽车,车棚的长度固定,但位置可以移动。目标是找到一种方式,使得车棚能够覆盖到最多的汽车数量。

输入

  • 一个整数N,表示汽车的数量。
  • 接下来N行,每行包含两个整数,分别表示每辆汽车的起始位置和结束位置(起始位置小于等于结束位置)。
  • 一个整数L,表示车棚的长度。

输出

  • 一个整数,表示车棚能够覆盖到的最多汽车数量。

示例

输入

4
1 3
2 6
8 10
5 9
5

解释

  • 有4辆汽车,位置分别为[1,3], [2,6], [8,10], [5,9]。
  • 车棚长度为5。

输出

3

解释

  • 车棚可以覆盖到[2,6](第2辆车)和[5,9](第4辆车),同时向右移动还可以覆盖到[8,10](第3辆车)的一部分,但由于车棚长度为5,所以无法完全覆盖第1辆车。因此,最多可以覆盖3辆车。

PHP代码示例:

<?php
function maxCarsCovered($cars, $L) {
    $n = count($cars);
    $maxCovered = 0;
    
    // 对每辆车的起始位置进行排序
    usort($cars, function($a, $b) {
        return $a[0] - $b[0];
    });
    
    $end = $cars[0][1]; // 当前车棚覆盖的最远位置
    $count = 1; // 当前车棚覆盖的汽车数量
    
    for ($i = 1; $i < $n; $i++) {
        // 如果当前车的起始位置在覆盖范围内,则增加计数
        if ($cars[$i][0] <= $end) {
            $count++;
            // 更新车棚的最远位置
            $end = max($end, $cars[$i][1]);
        } else {
            // 如果当前车不在覆盖范围内,尝试移动车棚到当前车开始
            // 检查如果移动后还能覆盖到之前的最后一辆车,则更新车棚位置
            if ($cars[$i][0] - $L <= $end) {
                $end = $cars[$i][1];
                $count = 1;
            } else {
                // 否则,重置车棚位置并重新开始计数
                $end = $cars[$i][1];
                $count = 1;
            }
        }
        $maxCovered = max($maxCovered, $count);
    }
    
    return $maxCovered;
}

// 示例输入
$cars = [[1, 3], [2, 6], [8, 10], [5, 9]];
$L = 5;
echo maxCarsCovered($cars, $L); // 输出: 3
?>

Python代码示例:

def max_cars_covered(cars, L):
    cars.sort(key=lambda x: x[0]) # 按起始位置排序
    max_covered = 0
    end = cars[0][1] # 初始最远位置
    count = 1 # 初始覆盖车辆数
    
    for i in range(1, len(cars)):
        if cars[i][0] <= end: # 如果新车在覆盖范围内
            count += 1
            end = max(end, cars[i][1]) # 更新最远位置
        else:
            # 如果新车不在覆盖范围内,尝试移动车棚
            if cars[i][0] - L <= end:
                end = cars[i][1]
                count = 1
            else:
                end = cars[i][1]
                count = 1
        max_covered = max(max_covered, count)
    
    return max_covered

# 示例输入
cars = [[1, 3], [2, 6], [8, 10], [5, 9]]
L = 5
print(max_cars_covered(cars, L)) # 输出: 3

JavaScript代码示例:

function maxCarsCovered(cars, L) {
    cars.sort((a, b) => a[0] - b[0]); // 按起始位置排序
    let maxCovered = 0;
    let end = cars[0][1]; // 初始最远位置
    let count = 1; // 初始覆盖车辆数
    
    for (let i = 1; i < cars.length; i++) {
        if (cars[i][0] <= end) { // 如果新车在覆盖范围内
            count++;
            end = Math.max(end, cars[i][1]); // 更新最远位置
        } else {
            // 如果新车不在覆盖范围内,尝试移动车棚
            if (cars[i][0] - L <= end) {
                end = cars[i][1];
                count = 1;
            } else {
                end = cars[i][1];
                count = 1;
            }
        }
        maxCovered = Math.max(maxCovered, count);
    }
    
    return maxCovered;
}

// 示例输入
const cars = [[1, 3], [2, 6], [8, 10], [5, 9]];
const L = 5;
console.log(maxCarsCovered(cars, L)); // 输出: 3

码小课网站中有更多相关内容分享给大家学习,涵盖算法、数据结构、编程技巧等各个方面,欢迎大家访问学习。

推荐面试题