▲

4

▼

🚗 Оптимальное распределение механиков с помощью эвристики и алгоритма QuickSelect 🛠️

leetcoder, 16-03-2025 , 579

Ссылка на задачу — 2594. Minimum Time to Repair Cars.

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

Дано:

• ranks — список рангов механиков.
• механик с рангом r может починить n машин за r * n² минут.
• cars — общее количество машин, ожидающих ремонта.

Нужно найти минимальное время, за которое все машины будут отремонтированы.
Предполагается, что все механики работают одновременно.

💡 Идея

Механики с меньшим рангом работают быстрее.
Произведём первичное распределение машин, используя обратный квадратный корень ранга как вес, определяющий долю машин, переданных каждому механику.

Однако это распределение не покрывает все машины. Для распределения оставшихся машин мы посчитаем для каждого механика оценку времени его работы, если взять несколько дополнительных машин (тем больше, чем больше вес механика). После остаётся лишь выбрать k-ое минимальное значение среди посчитанных времён с помощью алгоритма «QuickSelect» (любезно реализованного в стандартной библиотеке Rust).

🔍 Детали подхода

1️⃣ Быстрое распределение — вычисляем вес каждого механика и распределяем машины пропорционально.
2️⃣ Дополнительные оценки — для каждого механика предвычисляем возможные следующие времена ремонта (согласно весу механика).
3️⃣ Выбор оптимального времени — применяем метод из стандартной библиотеки select_nth_unstable, чтобы найти наилучшее время ремонта нераспределённых изначально машин.

⏳ Асимптотика

• Время: _O(N)
  • Первичное распределение: O(N)
  • Распределение оставшихся: O(N) — select_nth_unstable.
• Память: O(N)
  • Хранение времён для дополнительных возможных машин для каждого механика.

Замечание

У меня нет чёткого плана доказательства корректности эвристики с предрасчётом дополнительных машин для каждого из механиков. Но на всех разумных моих тестах и тестах с LeetCode эвристика успешно работает!

📝 Исходный код

impl Solution {
    pub fn repair_cars(ranks: Vec<i32>, mut cars: i32) -> i64 {
        // Normalization factor to weight mechanics by inverse square root of ranks.
        let weights_normalize: f64 = 1.0 / ranks.iter()
            .map(|&rank| (1.0 / rank as f64).sqrt())
            .sum::<f64>();

        let total_cars = cars as f64;
        let total_mechanics = ranks.len() as f64;
        let mut max_time = 0i64;
        let mut next_times = Vec::new();

        // Quickly assign cars based on mechanic ranks (weighted by inverse square root of rank).
        for &rank in &ranks {
            let weight = (1.0 / rank as f64).sqrt() * weights_normalize;
            let assigned = (total_cars * weight) as i32;
            cars -= assigned;

            let time = Self::repair_time(rank, assigned);
            max_time = max_time.max(time);

            // Determine the number of additional cars dynamically based on weight
            let additional_cars = (total_mechanics * weight).ceil() as i32; // Adjusted heuristic for next times
            for offset in 1..=additional_cars {
                next_times.push(Self::repair_time(rank, assigned + offset));
            }
        }

        // Determine final max time considering remaining cars
        if cars > 0 {
            let (_, nth_time, _) = next_times.select_nth_unstable(cars as usize - 1);
            max_time = max_time.max(*nth_time);
        }

        max_time
    }

    /// Calculates repair time for a given mechanic rank and number of cars
    fn repair_time(rank: i32, cars: i32) -> i64 {
        rank as i64 * (cars as i64).pow(2)
    }
}

Tags: #rust #algorithms #optimization #heuristics