题目描述补充:
题目:移动车棚
在一个水平直线上,停放着多辆汽车,每辆汽车占据一定的位置区间(即每辆车有一个起始位置和结束位置)。现在需要构建一个可移动的车棚来覆盖这些汽车,车棚的长度固定,但位置可以移动。目标是找到一种方式,使得车棚能够覆盖到最多的汽车数量。
输入:
- 一个整数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
码小课网站中有更多相关内容分享给大家学习,涵盖算法、数据结构、编程技巧等各个方面,欢迎大家访问学习。