坐上公交的最晚时间 2332
题目
给你一个下标从 0 开始长度为 n 的整数数组 buses ，其中 buses[i] 表示第 i 辆公交车的出发时间。同时给你一个下标从 0 开始长度为 m 的整数数组 passengers ，其中 passengers[j] 表示第 j 位乘客的到达时间。所有公交车出发的时间互不相同，所有乘客到达的时间也互不相同。
给你一个整数 capacity ，表示每辆公交车 最多 能容纳的乘客数目。
每位乘客都会搭乘下一辆有座位的公交车。如果你在 y 时刻到达，公交在 x 时刻出发，满足 y <= x 且公交没有满，那么你可以搭乘这一辆公交。最早 到达的乘客优先上车。
返回你可以搭乘公交车的最晚到达公交站时间。你 不能 跟别的乘客同时刻到达。
注意： 数组 buses 和 passengers 不一定是有序的。
示例 1：
输入： buses = [10,20], passengers = [2,17,18,19], capacity = 2
输出： 16
解释：
第 1 辆公交车载着第 1 位乘客。
第 2 辆公交车载着你和第 2 位乘客。
注意你不能跟其他乘客同一时间到达，所以你必须在第二位乘客之前到达。
示例 2：
输入： buses = [20,30,10], passengers = [19,13,26,4,25,11,21], capacity = 2
输出： 20
解释：
第 1 辆公交车载着第 4 位乘客。
第 2 辆公交车载着第 6 位和第 2 位乘客。
第 3 辆公交车载着第 1 位乘客和你。
提示：
n == buses.lengthm == passengers.length1 <= n, m, capacity <= 10^52 <= buses[i], passengers[i] <= 10^9buses中的元素 互不相同 。passengers中的元素 互不相同 。
分析与解答
总之既然是排队，怎么着也需要对乘客先排序。排序以后似乎顺序扫描过去就可以了。
排序复盘
排序是程序员基础中的基础了，要是问到排序还要想半天，实在是没有借口可以找了。写之前先对着下面的表过一下具体算法。
| 排序 | 复杂度 (最好) | 复杂度 (平均) | 复杂度 (最坏) | 复杂度（空间） | 稳定性 |
|---|---|---|---|---|---|
| 冒泡 | O(n) | O(n^2) | O(n^2) | O(1) | √ |
| 选择 | O(n^2) | O(n^2) | O(n^2) | O(1) | × |
| 插入 | O(n) | O(n^2) | O(n^2) | O(1) | √ |
| 归并 | O(n log n) | O(n log n) | O(n log n) | O(n) | √ |
| 快速 | O(n log n) | O(n log n) | O(n^2) | O(log n) | × |
| 堆 | O(n log n) | O(n log n) | O(n log n) | O(1) | × |
| 希尔 | O(n log n) | O(n^1.3) | O(n^2) | O(1) | × |
| 计数 | O(n+k) | O(n+k) | O(n+k) | O(k) | √ |
| 基数 | O(n * k) | O(n * k) | O(n * k) | O(n + k) | √ |
| 桶 | O(n + k) | O(n + k) | O(n^2) | O(n + k) | √ |
| 排序 | 说明 |
|---|---|
| 冒泡 | 通过多次遍历比较和交换相邻元素完成排序 |
| 选择 | 每次遍历选择最小元素放在已排序序列的末尾 |
| 插入 | 从未排序部分一个一个将元素插入到已排序序列中 |
| 归并 | 分治法，先递归分解再合并 |
| 快速 | 分治法，通过选取“基准”元素进行分区排序 |
| 堆 | 基于二叉堆的数据结构来进行选择排序 |
| 希尔 | 插入排序的改进版，通过间隔不断减少的子序列排序 |
| 计数 | 适用于整数排序，时间复杂度依赖于最大值k |
| 基数 | 对数字的每一位依次使用计数排序 |
| 桶 | 将数据分到多个桶中分别排序再合并 |
希尔排序
这个排序我上课的时候是没有学过的，虽然我好像也用过，但是记不太得了。
希尔排序是对插入排序的优化。典型方法是：首先设置一个gap，往往从数组长度一半开始。这样的话使用gap，将数组分成gap个成对元素。每个队进行插入排序，其实就是两个元素的比较。
然后逐渐减小gap直到1。简单的方法就是每次gap减半。
但是插入排序本身不怎么样，所以希尔排序并不是非常实用的样子。唯一的优点是无需额外空间，否则的话被思路类似的merge sort暴打。
快速排序
我觉得快速排序稍微特别一点，就简单提一下。
快速排序，首先估计一个中值，然后扫描一遍，将数据二分，然后递归。中值的估计非常影响算法效率，常见的方法是取第一个元素，但是我觉得在扫描的时候记录一个累积和然后取平均值可能可以带来优化。
排序代码
我们还是使用基本的冒泡。由于我上学的时候不许用STL，搞得我现在都不是很熟悉STL。
12345678910111213141516171819void swap(int& a, int& b) {
int temp = a;
a = b;
b = temp;
}
// or just use std::swap
// #include <algorithm>
void bubbleSort(vector<int>& arr) {
int n = arr.size();
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
swap(arr[j], arr[j + 1]);
}
}
}
}
// or just std::sort(arr.begin(), arr.end(), std::less<int>()); // 升序
冒泡排序还可以使用一个交换flag进行优化。如果一次遍历没有交换，说明已经有序了。
第一版代码
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950class Solution {
public:
int latestTimeCatchTheBus(vector<int>& buses, vector<int>& passengers, int capacity) {
bubbleSort(buses);
bubbleSort(passengers);
// sort(buses.begin(), buses.end());
// sort(passengers.begin(), passengers.end());
int n = buses.size();
int m = passengers.size();
int i = 0, j = 0; // 扫描用的pointer
int cur = 0; // 当前时间，是对于乘客而言的
int onB_bus = 0;
int latest = 0;
while (i < n && j < m) {
// new passenger
cur = max(cur, passengers[j]);
if (cur > buses[i]) {
// wait for new bus
onB_bus = 0;
while (i < n && buses[i] < cur) {
i++;
}
}
onB_bus += 1;
j++;
if (i < n && onB_bus == capacity) {
onB_bus = 0;
i++;
}
}
if (i == n) {
// the j-th passenger can't catch the bus, and we have to arrive before the previous one
latest = passengers[j - 1] - 1;
while (j - 2 >= 0 && latest == passengers[j - 2]) {
latest--;
j--;
}
if (latest >= buses[n - 1])
latest = buses[n - 1];
if (latest == passengers[0])
latest--;
}
else {
latest = buses[n - 1];
if (latest == passengers[m - 1])
latest--;
}
return latest;
}
};
由于要求不能同时到达（即使都上的去也不行）所以加了很长的判断。很搞笑的是我的sort会卡时间，结果还是用STL的sort。就结果而言内存和时间都不是很行。但是明天就要上课了。今天的论文还没改完。今天就先这样吧。