Задача с собеседования в Яндекс

Дана следующая структура мероприятий, имеющих временное начало и конец

struct Meeting {
    long long from;
    long long to;
}

vector<Meeting> crossing(const vector<Meeting>& meetings) ...

Необходимо найти пересекающиеся встречи

Наш чат алгоритмистов

Решение:
Сортируем встречи по времени начала, затем проходим слева направо, поддерживая наибольший правый конец max_end среди уже просмотренных интервалов и индекс того интервала, который даёт max_end. Если следующий интервал начинается раньше max_end, то он пересекается с каким-то предыдущим (в частности — с тем, чьё max_end), помечаем оба как пересекающиеся. В конце возвращаем (или выводим) все исходные встречи, помеченные как пересекающиеся.

Код:
vector<Meeting> crossing(const vector<Meeting>& meetings) {
int n = (int)meetings.size();
if (n == 0) return {};

// Соберём (from, to, orig_index) и отсортируем по from
struct Node { long long from, to; int idx; };
vector<Node> v;
v.reserve(n);
for (int i = 0; i < n; ++i) v.push_back({meetings[i].from, meetings[i].to, i});
sort(v.begin(), v.end(), [](const Node& a, const Node& b) {
if (a.from != b.from) return a.from < b.from;
return a.to < b.to;
});

vector<char> overlapped(n, 0); // пометки для исходных индексов

long long max_end = v[0].to;
int idx_max_sorted = 0; // индекс в v, который даёт max_end

// Считаем, что пересечение происходит если start < max_end (строгое пересечение).
// Если нужно считать касание по границе пересечением, менять на <= .
for (int i = 1; i < n; ++i) {
if (v[i].from < max_end) {
// v[i] пересекается с тем, у кого max_end
overlapped[v[i].idx] = 1;
overlapped[v[idx_max_sorted].idx] = 1;
}
if (v[i].to > max_end) {
max_end = v[i].to;
idx_max_sorted = i;
}
}

// Собираем результат в исходном порядке
vector<Meeting> res;
for (int i = 0; i < n; ++i) {
if (overlapped[i]) res.push_back(meetings[i]);
}
return res;
}

Время O(NlogN), память O(N)

@algoses