aboutsummaryrefslogtreecommitdiff
path: root/find_building_alice_bob_meet.cpp
blob: 9067bcf16aea5bc5046e70593225e3e71cdcaf7c (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
49
50
51
52
53
54
55
56
57
58
59
// 2940. Find Building Where Alice and Bob Can Meet
#include "leetcode.h"

/*
 * you are given a 0-indexed array 'heights' of positive integers where
 * 'heights[i]' represents the height of the i'th building. if a person is in
 * building 'i', they can move to any other building 'j' if and only if 'i < j'
 * and 'heights[i] < heights[j]'. you are also given an array 'queries' where
 * 'queries[i] = [a_i, b_i]'. on the i'th query, alice is in building 'a_i', and
 * bob is in building 'b_i'. return array 'ans' where 'ans[i]' is the index of
 * the leftmost building where alice and bob can meet on i'th query. if alice
 * and bob cannot move to a common building on query 'i', set 'ans[i]' to -1
 */

class Solution {
public:
  vector<int> leftmostBuildingQueries(vector<int> &heights,
                                      vector<vector<int>> &queries) {
    int hn = heights.size(), qn = queries.size();
    vector<vector<vector<int>>> q(hn);
    priority_queue<vector<int>, vector<vector<int>>, greater<vector<int>>> pq;
    vector<int> ans(qn, -1);
    for (int qi = 0; qi < qn; qi++) {
      int i = queries[qi][0], j = queries[qi][1];
      if (i < j && heights[i] < heights[j])
        ans[qi] = j;
      else if (i > j && heights[i] > heights[j])
        ans[qi] = i;
      else if (i == j)
        ans[qi] = i;
      else
        q[max(i, j)].push_back({max(heights[i], heights[j]), qi});
    }
    for (int i = 0; i < hn; i++) {
      while (!pq.empty() && pq.top()[0] < heights[i]) {
        ans[pq.top()[1]] = i;
        pq.pop();
      }
      for (auto &j : q[i])
        pq.push(j);
    }
    return ans;
  }
};

int main() {
  Solution obj;
  vector<int> h1 = {6, 4, 8, 5, 2, 7}, h2 = {5, 3, 8, 2, 6, 1, 4, 6};
  vvd(int) q1 = {{0, 1}, {0, 3}, {2, 4}, {3, 4}, {2, 2}},
           q2 = {{0, 7}, {3, 5}, {5, 2}, {3, 0}, {1, 6}};
  vector<int> lmbq1 = obj.leftmostBuildingQueries(h1, q1);
  vector<int> lmbq2 = obj.leftmostBuildingQueries(h2, q2);
  for (auto i : lmbq1)
    printf("%d ", i); // expect: 2 5 -1 5 2
  printf("\n");
  for (auto i : lmbq2)
    printf("%d ", i); // expect: 7 6 -1 4 6
  printf("\n");
}