2940. Find Building Where Alice and Bob Can Meet Hard

1/**
2 * [2940] Find Building Where Alice and Bob Can Meet
3 *
4 * You are given a 0-indexed array heights of positive integers, where heights[i] represents the height of the i^th building.
5 * 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].
6 * You are also given another array queries where queries[i] = [ai, bi]. On the i^th query, Alice is in building ai while Bob is in building bi.
7 * Return an array ans where ans[i] is the index of the leftmost building where Alice and Bob can meet on the i^th query. If Alice and Bob cannot move to a common building on query i, set ans[i] to -1.
8 *  
9 * <strong class="example">Example 1:
10 * 
11 * Input: heights = [6,4,8,5,2,7], queries = [[0,1],[0,3],[2,4],[3,4],[2,2]]
12 * Output: [2,5,-1,5,2]
13 * Explanation: In the first query, Alice and Bob can move to building 2 since heights[0] < heights[2] and heights[1] < heights[2]. 
14 * In the second query, Alice and Bob can move to building 5 since heights[0] < heights[5] and heights[3] < heights[5]. 
15 * In the third query, Alice cannot meet Bob since Alice cannot move to any other building.
16 * In the fourth query, Alice and Bob can move to building 5 since heights[3] < heights[5] and heights[4] < heights[5].
17 * In the fifth query, Alice and Bob are already in the same building.  
18 * For ans[i] != -1, It can be shown that ans[i] is the leftmost building where Alice and Bob can meet.
19 * For ans[i] == -1, It can be shown that there is no building where Alice and Bob can meet.
20 * 
21 * <strong class="example">Example 2:
22 * 
23 * Input: heights = [5,3,8,2,6,1,4,6], queries = [[0,7],[3,5],[5,2],[3,0],[1,6]]
24 * Output: [7,6,-1,4,6]
25 * Explanation: In the first query, Alice can directly move to Bob's building since heights[0] < heights[7].
26 * In the second query, Alice and Bob can move to building 6 since heights[3] < heights[6] and heights[5] < heights[6].
27 * In the third query, Alice cannot meet Bob since Bob cannot move to any other building.
28 * In the fourth query, Alice and Bob can move to building 4 since heights[3] < heights[4] and heights[0] < heights[4].
29 * In the fifth query, Alice can directly move to Bob's building since heights[1] < heights[6].
30 * For ans[i] != -1, It can be shown that ans[i] is the leftmost building where Alice and Bob can meet.
31 * For ans[i] == -1, It can be shown that there is no building where Alice and Bob can meet.
32 * 
33 *  
34 * Constraints:
35 * 
36 * 	1 <= heights.length <= 5 * 10^4
37 * 	1 <= heights[i] <= 10^9
38 * 	1 <= queries.length <= 5 * 10^4
39 * 	queries[i] = [ai, bi]
40 * 	0 <= ai, bi <= heights.length - 1
41 * 
42 */
43pub struct Solution {}
44
45// problem: https://leetcode.com/problems/find-building-where-alice-and-bob-can-meet/
46// discuss: https://leetcode.com/problems/find-building-where-alice-and-bob-can-meet/discuss/?currentPage=1&orderBy=most_votes&query=
47
48// submission codes start here
49
50impl Solution {
51    pub fn leftmost_building_queries(heights: Vec<i32>, queries: Vec<Vec<i32>>) -> Vec<i32> {
52        vec![]
53    }
54}
55
56// submission codes end
57
58#[cfg(test)]
59mod tests {
60    use super::*;
61
62    #[test]
63    fn test_2940() {
64    }
65}
66