История одной задачи.
Условие: вводят n отрезков в виде левой и правой границ и m точек.
Для каждой точке в порядке ввода вывести количество отрезков, которым принадлежит точка.
Итерации:
1) В цикле ввод границ отрезков в одномерный массив вида i*n+j (а-ка двумерный) и координаты точки. Наивный алгоритм поиска перебором по всем точкам со сравнениями по границам отрезка.
Не проходит по времени.
2) Делаем быструю сортировку (самописную). Сортируем по левым границам, поиск перебором точек >= левой границы и сортируем по правым границам, ищем > правой границы, находим разницу величин. Идею придумал сам, но полез в комментарии убедиться. Убедился.
Не проходит по времени.
3) Делаю элиминацию хвостовой рекурсии в быстрой сортировке.
Не проходит по времени.
4) Делаю учет элементов массива, равных ключевому, в быстрой сортировке с последующим откидыванием.
Не проходит по времени.
5) Делаю выбор ключевого элемента как (left+right)/2.
Не проходит по времени.
6) Заменяю перебор точек на бинарный поиск.
Не проходит по времени.
7) В голову входит мысль, что множество отрезков на самом деле едино для всех точек, а не вводятся каждый раз для новой точки. Выкидываю двумерный массив, делаю два для левой и правой границ, сортирую их заранее.
Тесты проходит.
Ура, что ли.
~6 часов без наведения красоты. С красотой еще помучился, ибо заводить две функции, различающиеся один знаком как-то не хотелось, но придумать красивый вариант не получилось.