aboutsummaryrefslogtreecommitdiff
path: root/latest_time_catch_bus.c
blob: 0f280d69b3f3161e68e89049a312cd8f01b8130f (plain)
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
}