Спершу пригадаємо класичний факт про відрізки: набір відрізків має спільну точку попарно тоді й лише тоді, коли він має спільну точку всі разом. А це рівносильно простій умові
Справді, якщо максимум лівих кінців не перевищує мінімуму правих, то будь-яка точка між ними належить усім відрізкам; і навпаки, якщо \max l > \min r, то відрізок з найбільшим лівим кінцем і відрізок з найменшим правим не перетинаються.
Отже, задача звелася до такого: серед N+1 відрізків знайти той, після видалення якого виконується \max l \le \min r.
Перебирати кандидата й щоразу перераховувати максимум і мінімум з нуля — це \mathcal{O}(N^2). Замість цього скористаємось префіксними та суфіксними величинами. Порахуємо:
, — максимум лівих і мінімум правих кінців серед перших відрізків;
, — те саме для відрізків з -го до останнього.
Тоді після видалення відрізка отримуємо
і умову перевіряємо за .
Загальна складність — . Якщо підходять кілька відрізків, виводьте будь-який згідно з форматом умови.