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

Автор темы Felimog 
ОбъявленияПоследний пост
ОбъявлениеHuawei - Research scientist (math)22.06.2021 11:25
ОбъявлениеПостдок позиция по математике в Гетеборге (Швеция)10.09.2021 19:11
ОбъявлениеPostdoc: Stochastics and algorithmics behind network problems (Netherlands)08.10.2021 08:36
16.02.2004 08:41
Felimog
Даны k отрезков ...
Даны k отрезков. За время (!)меньшее(!) o(k*k) найти максимальное число n для которого существует точка, принадлежащая n отрезкам.
16.02.2004 15:57
k*ln(k)
Быстрой сортировкой сортируешь вместе левые и правые концы отрезков, храня инфу о том, какие из них - левые, а какие - правые, и проходишь по всему диапазону со счётчиком, который на левых концах возрастает на 1, а на правых - убывает.
Извините, только зарегистрированные пользователи могут публиковать сообщения в этом форуме.

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