1
class Solution {
2
 public:
3
  int latestTimeCatchTheBus(vector<int> &buses, vector<int> &passengers, int capacity) {
4
    queue<int> q;
5
    sort(buses.begin(), buses.end());
6
    sort(passengers.begin(), passengers.end());
7
    int n = buses.size();
8
    int m = passengers.size();
9
    set<int> st;
10
    for (auto p : passengers) {
11
      q.push(p);
12
      st.insert(p);
13
    }
14
    int ans = 0;
15
    for (int i = 0; i < n; i++) {
16
      int currbus = buses[i]; // curr bus depature time.
17
      int count = 0;          // number of people in curr bus
18
      int x;
19
      // CASE1
20
      while (!q.empty() && count < capacity && q.front() <= currbus) {
21
        x = q.front();
22
        q.pop();
23
        if (st.find(x - 1) == st.end()) // checking if person timing-1 doesnt
24
                                        // exist and update the answer.
25
          ans = x - 1;
26
        count++;
27
      }
28
      // CASE2
29
      if (count < capacity) {
30
        while (st.find(currbus) != st.end()) // starting from dept time find a time which does not
31
                                             // exist int the set already.
32
        {
33
          currbus--;
34
        }
35
        ans = max(ans, currbus);
36
      }
37
    }
38
    return ans;
39
  }
40
};