1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
|
// 2332. The Latest Time to Catch a Bus
#include "leetcode.h"
/*
* given a 0-indexed array 'buses' of length 'n' where 'buses[i]' represents the
* departure time of the i'th bus. you are also given a 0-indexed array
* 'passengers' of length 'm' where 'passengers[j]' represents the arrival time
* of the j'th passenger. all bus departure times are unique. all passenger
* arrival times are unique. return the latest time you may arrive at the bus
* station to catch a bus. you cannot arrive at the same time as another
* passenger.
*/
int cmp(const void *a, const void *b) {
if (*(int *)a == *(int *)b)
return 0;
return *(int *)a < *(int *)b ? -1 : 1;
}
int latestTimeCatchTheBus(int *buses, int busesSize, int *passengers,
int passengersSize, int capacity) {
qsort(buses, busesSize, sizeof(int), cmp);
qsort(passengers, passengersSize, sizeof(int), cmp);
int p = 0, last_board = -1, last_bus = busesSize - 1, j;
for (int i = 0; i < busesSize; i++)
for (j = 0; j < capacity && p < passengersSize && passengers[p] <= buses[i];
j++) {
last_board = i;
p++;
}
if (last_board != last_bus)
return buses[last_bus];
p--;
if (j < capacity && passengers[p] + 1 <= buses[last_board])
return buses[last_board];
while (p && passengers[p] - 1 == passengers[p - 1])
p--;
return passengers[p] - 1;
}
int main() {
int b1[] = {10, 20}, p1[] = {2, 17, 18, 19}, b2[] = {20, 30, 10},
p2[] = {19, 13, 26, 4, 25, 11, 21};
printf("%d\n", latestTimeCatchTheBus(b1, ARRAY_SIZE(b1), p1, ARRAY_SIZE(p1),
2)); // expect: 16
printf("%d\n", latestTimeCatchTheBus(b2, ARRAY_SIZE(b2), p2, ARRAY_SIZE(p2),
2)); // expect: 20
}
|