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

Автор темы Felimog 
ОбъявленияПоследний пост
ОбъявлениеПреподаватель мехмата МГУ удостоен международной премии по математике Presburger Award28.07.2020 01:04
ОбъявлениеHuawei - Research scientist (math)22.06.2021 11:25
ОбъявлениеЧисло «Пи» рассчитано с рекордной точностью на «бюджетном» компьютере27.08.2021 22:26
16.02.2004 08:41
Felimog
Даны k отрезков ...
Даны k отрезков. За время (!)меньшее(!) o(k*k) найти максимальное число n для которого существует точка, принадлежащая n отрезкам.
16.02.2004 15:57
k*ln(k)
Быстрой сортировкой сортируешь вместе левые и правые концы отрезков, храня инфу о том, какие из них - левые, а какие - правые, и проходишь по всему диапазону со счётчиком, который на левых концах возрастает на 1, а на правых - убывает.
Извините, только зарегистрированные пользователи могут публиковать сообщения в этом форуме.

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