CSES - Restaurant Customers

Решал эту задачу. Вот мой код. Проходит все кроме шестого теста, а это макс тест. Я сжимаю координаты от 0 до 2n-1 и сортирую отрезки по оригинальным значениям. Что я делаю не так?

Ты как находишь максимальное количество покупателей? Разве не легче просто сжать координаты и потом найти все сканлайном

с помощью двух указателей
после того, как я сжал отрезки я увеличиваю праву границу и уменьшаю левую, если не все отрезки [l; r] пересекаются(max(l) > min(r))

Это та же самая задача что и точка покрытая наибольшим количеством отрезков. Думаю легче будет решить не двумя указателями, а как сказал Еларыс сканлайном.
Создай массив пар в котором ты будешь хранить: X - координаты всех границ, type означающий является ли эта координата началом или концом отрезка. -1 в случае если это конец отрезка и 1 если это начало отрезка. Отсортируй его.
Затем проходя по нему слева на права и параллельно храни переменную cnt = 0. Если координата которую ты встретил это левая граница(то есть 1) тогда прибавь эту единицу к cnt. Если координата которую ты встретил это правая граница (то есть -1) тогда отними единицу от cnt. Момент в котором cnt максимально это и есть ответ

Большое желание написать еще один ответ с сканлайном… Но я держусь…

1 лайк

Сканлайн

2 лайка