MiddleКодИногдаЕщё не отвечали
Вернуть все встречи, пересекающиеся хотя бы с одной другой
Дан список встреч с полуоткрытыми интервалами [from, to). Верните множество встреч, пересекающихся хотя бы с одной другой. Улучшите наивную проверку всех пар за O(n^2).
Требования:
- Две встречи пересекаются тогда и только тогда, когда их полуоткрытые интервалы пересекаются.
- Цель — O(n log n) по времени.
struct Meeting { long from, to; };
std::vector<Meeting> crossing(std::vector<Meeting> meetings) {
// ваш код здесь
}Допишите реализацию.
Сортируем по from, затем проходим, отслеживая текущий максимум to среди ранее начавшихся встреч. Встреча пересекает более раннюю, когда её from < maxEnd; тогда помечаем и её, и встречу, задавшую maxEnd. Флаг на встречу гарантирует один отчёт на каждую. O(n log n).
- ✗Сравнивать только соседние отсортированные интервалы, пропуская встречу, пересечённую более ранней несоседней
- ✗Смешивать проверки замкнутых и полуоткрытых границ, из-за чего касающиеся интервалы ошибочно считаются пересекающимися
- ✗Сообщать встречу дважды, когда она пересекает несколько других
- →Как полуоткрытое правило
[from, to)меняет сравнение границ? - →Чем это отличается от поиска максимального числа одновременных встреч?
Оглавление
Задача
Верните все встречи, пересекающиеся хотя бы с одной другой; быстрее наивного O(n^2).
Решение
#include <vector>
#include <algorithm>
struct Meeting { long from, to; };
std::vector<Meeting> crossing(std::vector<Meeting> meetings) {
size_t n = meetings.size();
std::vector<size_t> idx(n);
for (size_t i = 0; i < n; ++i) idx[i] = i;
std::sort(idx.begin(), idx.end(),
[&](size_t a, size_t b){ return meetings[a].from < meetings[b].from; });
std::vector<bool> hit(n, false);
long maxEnd = -1; size_t maxIdx = 0;
for (size_t k = 0; k < n; ++k) {
size_t i = idx[k];
if (k > 0 && meetings[i].from < maxEnd) { // полуоткрытое: < конца
hit[i] = true; hit[maxIdx] = true;
}
if (meetings[i].to > maxEnd) { maxEnd = meetings[i].to; maxIdx = i; }
}
std::vector<Meeting> res;
for (size_t i = 0; i < n; ++i) if (hit[i]) res.push_back(meetings[i]);
return res;
}Ключевые моменты
- Сортировка по началу + текущий максимум конца ловит и несоседние пересечения.
- Полуоткрытое
[from, to): касание границ не есть пересечение. - Флаг на встречу гарантирует один отчёт на встречу.
Оглавление
