Даны k отрезков ...

Автор темы Felimog 
ОбъявленияПоследний пост
ОбъявлениеЗапущен новый раздел «Задачки и головоломки»29.08.2019 00:42
ОбъявлениеПреподаватель мехмата МГУ удостоен международной премии по математике Presburger Award28.07.2020 01:04
ОбъявлениеГранты для студентов и аспирантов мехмата и физфака МГУ на обучение в магистратуре Кембриджа 2022/202314.10.2021 12:28
16.02.2004 08:41
Felimog
Даны k отрезков ...
Даны k отрезков. За время (!)меньшее(!) o(k*k) найти максимальное число n для которого существует точка, принадлежащая n отрезкам.
16.02.2004 15:57
k*ln(k)
Быстрой сортировкой сортируешь вместе левые и правые концы отрезков, храня инфу о том, какие из них - левые, а какие - правые, и проходишь по всему диапазону со счётчиком, который на левых концах возрастает на 1, а на правых - убывает.
Извините, только зарегистрированные пользователи могут публиковать сообщения в этом форуме.

Кликните здесь, чтобы войти