🏙️ Эффективное разрешение отложенных запросов с использованием двоичной кучи

leetcoder, 9 ч назад ,

Описание задачи 📝

У нас есть массив heights, где heights[i] представляет высоту здания i.
Также даны запросы в виде массива queries, где каждый запрос [a_i,b_i>] требует определить самое левое здание, на которое могут попасть Алиса и Боб, начав с a_i и b_i соответственно, при соблюдении следующих условий:

Алиса и Боб могут двигаться только в здания с индексами больше их текущего.
Они могут перейти только на здания с высотой больше их текущей.

Если подходящее здание невозможно найти, результат для данного запроса равен −1.

Идея 💡

Мне сходу не известна эффективная структура данных для онлайн-разрешения запросов.
Но можно поступить хитрее, а именно:

Немедленно обработать "простые" запросы, где результат очевиден.
Для сложных запросов использовать технику отложенной обработки:
- Сначала отсортировать их по индексу правого здания.
- Затем разрешать запросы, итерируясь по зданиям, и, храня кандидатов на разрешение в двоичной куче.

Детали подхода 🛠️

Предварительная обработка запросов:
- Разделяем запросы на "простые" и "сложные". "Простые" запросы немедленно записываем в результат.
- "Сложные" запросы сохраняем как структуры MaxQuery для последующей обработки.
Сортировка запросов:
- Сортируем "сложные" запросы по индексу правого здания.
Решение с помощью кучи:
- Итеративно проходим по массиву зданий (heights).
- Для каждого здания:
  - Добавляем в кучу все запросы, которые нужно обработать, начиная с текущего индекса.
  - Разрешаем запросы в куче, проверяя минимальную высоту из запроса по сравнению с текущей высотой здания.

Асимптотика ⏱️💾

Временная сложность:
- Сортировка запросов: O(q·log⁡ q), где q — количество запросов.
- Операции с кучей (добавление и удаление): O(q·log ⁡q).
- Итерация по зданиям с O(1) проверкой: O(n) где n — количество зданий.
- Общая сложность: O(n + q·log⁡ q).
Пространственная сложность:
- Куча для хранения запросов: O(q).
- Вспомогательные структуры данных: O(q).
- Общая сложность: O(q).

Исходный код решения 💻

use std::collections::BinaryHeap;

#[derive(Eq, PartialEq, Clone)]
struct MaxQuery {
    value: i32,
    index: usize,
    query_idx: usize,
}

impl Solution {
    pub fn leftmost_building_queries(heights: Vec<i32>, queries: Vec<Vec<i32>>) -> Vec<i32> {
        let mut results = vec![-1; queries.len()];
        let mut deferred_queries = Vec::new();

        // Prepare queries
        for (idx, query) in queries.iter().enumerate() {
            let (mut l, mut r) = (query[0] as usize, query[1] as usize);
            if l > r {
                (l, r) = (r, l);
            }
            if l == r || heights[r] > heights[l] {
                results[idx] = r as i32;
            } else {
                deferred_queries.push(MaxQuery::new(heights[l], r, idx));
            }
        }

        // Sort deferred queries by index
        deferred_queries.sort_by_key(|q| q.index);

        // Process queries using a heap
        let mut heap = BinaryHeap::new();
        let mut deferred_idx = 0;

        for (current_idx, &height) in heights.iter().enumerate() {
            // Add all queries up to the current position
            while deferred_idx < deferred_queries.len()
                && deferred_queries[deferred_idx].index <= current_idx
            {
                heap.push(deferred_queries[deferred_idx].clone());
                deferred_idx += 1;
            }

            // Resolve queries in the heap
            while let Some(top_query) = heap.peek() {
                if top_query.value < height {
                    results[top_query.query_idx] = current_idx as i32;
                    heap.pop();
                } else {
                    break;
                }
            }
        }

        results
    }
}

impl MaxQuery {
    fn new(value: i32, index: usize, query_idx: usize) -> Self {
        Self{value, index, query_idx}
    }
}

impl Ord for MaxQuery {
    fn cmp(&self, other: &Self) -> std::cmp::Ordering {
        other.value.cmp(&self.value)
    }
}

impl PartialOrd for MaxQuery {
    fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
        Some(self.cmp(other))
    }
}