Ссылка на задачу — 3480. Maximize Subarrays After Removing One Conflicting Pair.
📌 Описание задачи
- Дан массив чисел от
1 до n и список конфликтных пар conflicting_pairs,
где каждая пара [a, b] запрещает подотрезки[1, n] , в которых a и b встречаются совместно.
- Требуется удалить ровно одну конфликтную пару так,
чтобы получить максимальное количество подотрезков из [1, n], удовлетворяющих оставшимся ограничениям.
Пример
- Входные параметры:
n = 5, conflictingPairs = [[1,2],[2,5],[3,5]]
- Ответ:
12
- Объяснение:
Удаляем [1, 2] из массива конфликтных пар. Остаются: [[2, 5], [3, 5]].
Всего 12 подотрезков удовлетворяют условию не содержать одновременно 2 и 5 или 3 и 5.
Это отрезки: 1..1, 1..2, 1..3, 1..4, 2..2, 2..3, 2..4, 3..3, 3..4, 4..4, 4..5, 5..5
💡 Идея
- Ключевое наблюдение заключается в том, что конфликтные пары создают ограничения на диапазоны, ограничивая допустимые подотрезки.
- Мы обрабатываем левые границы возможных подотрезков в обратном порядке (от
n до 1), отслеживая разрешенную правую границу для подотрезков и коррекцию для текущего активного ограничения.
- Таким образом, мы можем выбрать ограничение (конфликтную пару), удаление которого даст наибольший прирост в количестве допустимых подотрезков.
🛠 Детали подхода
1️⃣ Нормализация пар → Преобразуем каждую пару в вид [меньшее, большее], чтобы гарантировать корректную обработку.
2️⃣ Сортировка конфликтных пар → в убывающем порядке по левой границе (-p[0]).
3️⃣ Обратный обход левых границ (от n до 1) → Поддерживаем правую границу допустимого диапазона динамически.
4️⃣ Коррекция штрафов → Используем active_correction и cur_penalty, чтобы учитывать возможное улучшение от удаления текущего активного ограничения.
5️⃣ Финальный подсчет → Возвращаем valid_subarrays + max_penalty, где max_penalty — наибольшее количество подотрезков, которое можно получить, удалив одну конфликтную пару.
⏳ Асимптотика
-
Общее время работы:
O(n+k·logk).
- Сортировка пар:
O(k·logk), где k — количество конфликтных пар.
- Обход по границам:
O(n+k).
-
Дополнительная память:
O(1)
- Xраним только несколько переменных.
💻 Исходный код
impl Solution {
pub fn max_subarrays(n: i32, mut conflicting_pairs: Vec<Vec<i32>>) -> i64 {
// Ensure each conflicting pair is sorted as [smaller, larger]
for pair in conflicting_pairs.iter_mut() {
if pair[0] > pair[1] {
pair.swap(0, 1);
}
}
// Sort conflicting pairs in descending order (so we can iterate forward)
conflicting_pairs.sort_unstable_by_key(|p| -p[0]);
let mut conflict_pairs_iter = conflicting_pairs.into_iter().peekable();
let mut right_boundary = n + 1; // Rightmost valid range
let mut active_correction = 0;
let mut valid_subarrays: i64 = 0;
let mut cur_penalty: i64 = 0;
let mut max_penalty: i64 = 0;
// Traverse from n down to 1
for b in (1..=n).rev() {
// Process conflicting pairs affecting `b`
while let Some(p) = conflict_pairs_iter.next_if(|p| p[0] >= b) {
if right_boundary > p[1] {
// Found a new correction point
active_correction = right_boundary - p[1];
right_boundary = p[1];
cur_penalty = 0; // Reset penalty when a new correction starts
} else {
// Minimize the correction penalty
active_correction = active_correction.min(p[1] - right_boundary);
}
}
valid_subarrays += (right_boundary - b) as i64;
cur_penalty += active_correction as i64;
max_penalty = max_penalty.max(cur_penalty);
}
valid_subarrays + max_penalty
}
}
Tags: #rust #algorithms #optimization