Leetcode 2940. Find Building Where Alice and Bob Can Meet

문제

You are given a 0-indexed array heights of positive integers, 
where heights[i] represents the height of the ith 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 another array queries where queries[i] = [ai, bi]. 
On the ith query, Alice is in building ai while Bob is in building bi.

Return an array ans where ans[i] is the index of the leftmost building where Alice and Bob can meet on the ith query. 
If Alice and Bob cannot move to a common building on query i, set ans[i] to -1.

• 빌딩 여러개와 그 빌딩의 높이가 주어진다.
• 빌딩은 반드시 오른쪽, 자신보다 높은 빌딩으로만 이동 가능하다.
• 두 사람의 위치가 쿼리로 주어질때 두 사람이 만날수 있는 가장 왼쪽의 빌딩의 index를 답에 채워라
  • 단 없으면 -1

예시

• 너무 복잡한 관계로
  https://leetcode.com/problems/find-building-where-alice-and-bob-can-meet/?envType=daily-question&envId=2024-12-22
  직접 참조

제한

• $1 <= heights.length <= 5 * 10^4$
• $1 <= heights[i] <= 10^9$
• $1 <= queries.length <= 5 * 10^4$
• $queries[i] = [ai, bi]$
• $0 <= a_i, b_i <= heights.length - 1$

풀이

• 이 문제의 본질을 이해하면 다음과 같다.
  • 주어진 쿼리의 두 값 a, b 가 각각 작은값이 a, 큰값이 b라고 가정한다.
  • heights[a] 와 heights[b] 중 큰 값에 대해 b~height의 끝 까지 중 가장 먼저 이 큰 값보다 절대적으로 큰 값의 위치가 쿼리의 정답이다.

class Solution:
    def leftmostBuildingQueries(self, heights: List[int], queries: List[List[int]]) -> List[int]:
        N = len(queries)

        ans = [-1] * N

        group = defaultdict(list)

        for i, v in enumerate(queries):
            l, r = sorted(v)

            if l == r or heights[l] < heights[r]:
                ans[i] = r
            else:
                group[r].append((max(heights[l], heights[r]), i))

        heap = []

        for i, v in enumerate(heights):

            for target, index in group[i]:
                heappush(heap, (target, index))

            while heap and v > heap[0][0]:
                _, point = heappop(heap)
                ans[point] = i

        return ans

• ans : 정답이 들어갈 공간 ( 기본값 -1 )
• group : group의 index i 는 i번 인덱스부터 확인 할 것이라는것을 뜻한다.

        for i, v in enumerate(queries):
            l, r = sorted(v)

            if l == r or heights[l] < heights[r]:
                ans[i] = r
            else:
                group[r].append((max(heights[l], heights[r]), i))

• 두 위치가 같으면 이미 같으므로, 정답이 정해지고, 오른쪽이 더 크다면 이또한 바로 정해진다.
• 이외엔 그룹에 추가

        for i, v in enumerate(heights):

            for target, index in group[i]:
                heappush(heap, (target, index))

            while heap and v > heap[0][0]:
                _, point = heappop(heap)
                ans[point] = i

• height을 순회하다 검사를 해야할 구간에 도달하면 heap에 추가하고 가장 작은것부터 검사해서 답에 추가한다.