Comments / Profile of wataru / Habr

C++ разработчик.

Задача о пересечении интервалов (или зачем программисту MК стабильная сортировка)

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

bool less(Event a, Event b) {
  if (a.time < b.time) return true;
  if (a.time > b.time) return false;
  if (a.type < b.type) return true;
  if (a.tupe > b.type) return false;
  return a.id < b.id;
}

Можно это вставить в свою сортировку, а можно функцию сравнения передать тому же qsort (правда, в C надо будет изменить ее возвращать не true/false, а отрицательное/нулевое/положительное число).

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

Более простой метод: все отрезки отсортировать по началу, потом пройтись по массиву один раз и проверять каждые 2 соседних отрезка на пересечение через min/max начал и концов:

bool Intersects(Segment a, Segment b) {
  return min(a.right, b.right) >= max(a.left, b.left);
}

Это работает, потому что самый левый отрезок, если и пересекается с каким-то орезком, то пересекается и со всеми, левее него. А значит точно есть пересечение и со вторым отрезком в отсортированном массиве. Если же первый отрезок не пересекается со вторым, то не пересекается и с любым следующим, ведь они еще правее второго. Дальше можно первый отрезок исключить из рассмотрения и применить ту же логику опять.