目录

题目

思路

Code

题目

题目内容：

小明自驾回家，为节省旅途成本，决定在网上挂出顺风车服务。

有需要的乘客可自行申请服务，由小明决定谁能搭乘顺风车。

请设计程序帮助小明将顺风车收益最大化，并返回最大的顺风车收益。

路线统一采用数值表示，小明的起点为 0，终点为 n。

乘客起点和终点必须在 0 到 n 之间，且终点值大于起点值。

由于小明有家人同行，同一时间段只有一个乘客可以搭乘顺风车。

终点数值和起点数值差是乘车距离，单位为公里。

每公里顺风车小明收费 1 元。

输入描述：

输入包含 n 和 passengers。

n 是整数，表示小明的终点位置，值大于 1 且小于 1000。

passengers 是乘客申请列表，每个乘客由起点和终点组成，乘客数量不超过 300。

输入可写为 10,[[0,3],[1,4]] 这种形式。

输出描述：

输出整数，表示小明该趟顺风车的最大收益。

样例 1

输入：

10,[[0,3],[1,4],[3,8],[5,10]]

输出：

8

说明：

可以选择 0 到 3 和 3 到 8，或选择 1 到 4 和 5 到 10，最大收益为 8。

样例 2

输入：

10,[[0,5],[1,2],[3,6],[5,8],[6,10]]

输出：

9

说明：

选择 0 到 5 和 6 到 10，总收益为 9。

样例 3

输入：

20,[[0,5],[5,10],[10,15]]

输出：

15

说明：

三个乘客区间互不重叠，可以全部选择。

思路

整体思路：每个乘客申请是一个带收益区间，收益为 end 减 start，问题是带权区间调度。

第一步：把乘客按终点从小到大排序，保证处理当前乘客时，可兼容的乘客都在前面。

第二步：令 dp[i] 表示只考虑前 i 个乘客可获得的最大收益。

第三步：对当前乘客，用二分找到最后一个终点小于等于当前起点的乘客数量。

第四步：比较不选当前乘客的 dp[i-1] 和选择当前乘客的 dp[k] 加当前收益。

边界处理：终点等于下一个起点不算重叠，可以连续搭载。

复杂度分析：排序和每次二分的时间复杂度为 O(m log m)，空间复杂度为 O(m)。

Code

import bisect
import re
import sys

# 从形如 10,[[0,3],[3,8]] 的输入中提取全部数字。
nums = list(map(int, re.findall(r"\d+", sys.stdin.read())))
if not nums:
    print(0)
    sys.exit()
n = nums[0]
rides = []
for i in range(1, len(nums) - 1, 2):
    s, e = nums[i], nums[i + 1]
    # 只保留题目范围内的有效乘客申请。
    if 0 <= s < e <= n:
        rides.append((s, e))
# 按终点排序后，可以用前缀 dp 表示已处理乘客的最优收益。
rides.sort(key=lambda x: x[1])
ends = [e for _, e in rides]
dp = [0] * (len(rides) + 1)
for i, (start, end) in enumerate(rides, 1):
    # 找到最后一个终点不晚于当前起点的乘客数量。
    # 终点等于当前起点可以连续接载，因此用 bisect_right。
    prev = bisect.bisect_right(ends, start, 0, i - 1)
    take = dp[prev] + end - start
    # 当前乘客可选可不选，保留收益更高的方案。
    dp[i] = max(dp[i - 1], take)
print(dp[-1])

JS

const fs = require("fs");

// 输入中的括号只描述列表结构，提取数字后按顺序两两组成区间。
const nums = (fs.readFileSync(0, "utf8").match(/\d+/g) || []).map(Number);
if (nums.length === 0) {
  console.log(0);
  process.exit(0);
}
const n = nums[0];
const rides = [];
for (let i = 1; i + 1 < nums.length; i += 2) {
  if (nums[i] < nums[i + 1] && nums[i + 1] <= n) rides.push([nums[i], nums[i + 1]]);
}
// 按终点排序，后续 dp 只依赖前面乘客。
// 终点升序后，能与当前乘客兼容的区间都在前缀中。
rides.sort((a, b) => a[1] - b[1]);
const ends = rides.map(r => r[1]);
const dp = Array(rides.length + 1).fill(0);
for (let i = 1; i <= rides.length; i++) {
  const [start, end] = rides[i - 1];
  let left = 0, right = i - 2, prev = 0;
  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    // end 等于 start 时不重叠，可以连续接载。
    if (ends[mid] <= start) { prev = mid + 1; left = mid + 1; }
    else right = mid - 1;
  }
  // 选择当前乘客时，只能叠加到最后兼容前缀的收益上。
  const take = dp[prev] + end - start;
  // 不选当前乘客与选择当前乘客取较大值。
  dp[i] = Math.max(dp[i - 1], take);
}
console.log(dp[rides.length]);

【华为od机试真题Python+JS+Java+Go合集】【超值优惠】：Py/JS/Java/Go合集

【华为od机试真题Python】：Python真题题库

【华为od机试真题JavaScript】：JavaScript真题题库

【华为od机试真题Java&Go】：Java&Go真题题库

【华为od机试真题C++】：C++真题题库

【华为od机试真题C语言】：C语言真题题库

【华为od面试手撕代码题库】：面试手撕代码题库

【华为od机试面试交流群】【文章底部有二维码链接，可扫码加交流群】

华为OD机试:二本院校有机会吗? 有机会,但不大,大神除外!机考分数越高越好,所以需要提前刷题。机考通过后,如果没有收到面试邀请,也不要着急,非目标院校面试邀请发的时间比较晚。非目标院校今年有点难,机试至少要考到350分,所以需要疯狂刷题,华为OD机考是有题库的,最好在考前完所有题库题目。华为OD机试:跨专业可以参加华为OD可以,但是如果你的本科院校比较差,上岸概率不大。华为OD机试:华为OD简历被锁定机试通过,性格测试也通过,但是没人联系面试,发现简历被锁定。此时需要主动去联系HR。让他帮助你查询原因。