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

Автор темы Felimog 
ОбъявленияПоследний пост
ОбъявлениеМатематики, программисты, репетиторов (платформа SapioX)28.01.2021 12:47
ОбъявлениеЧисло «Пи» рассчитано с рекордной точностью на «бюджетном» компьютере27.08.2021 22:26
ОбъявлениеПостдок позиция по математике в Гетеборге (Швеция)10.09.2021 19:11
16.02.2004 08:41
Felimog
Даны k отрезков ...
Даны k отрезков. За время (!)меньшее(!) o(k*k) найти максимальное число n для которого существует точка, принадлежащая n отрезкам.
16.02.2004 15:57
k*ln(k)
Быстрой сортировкой сортируешь вместе левые и правые концы отрезков, храня инфу о том, какие из них - левые, а какие - правые, и проходишь по всему диапазону со счётчиком, который на левых концах возрастает на 1, а на правых - убывает.
Извините, только зарегистрированные пользователи могут публиковать сообщения в этом форуме.

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