|
⇤ ← Версия 1 от 2019-10-17 22:57:40
Размер: 1074
Комментарий:
|
← Версия 2 от 2019-10-17 22:58:11 ⇥
Размер: 1080
Комментарий:
|
| Удаления помечены так. | Добавления помечены так. |
| Строка 9: | Строка 9: |
| Здесь имеются три группы накладывающихся отрезков: `(18, 58), (21, 81), (66, 91)`, `(152, 230), (158, 211), (183, 236)` и `(286, 332), (294, 330), (323, 342)`. Их длины `91-18+236-152+342-286=213` | Здесь имеются три группы накладывающихся отрезков: `((18, 58), (21, 81), (66, 91))`, `((152, 230), (158, 211), (183, 236))` и `((286, 332), (294, 330), (323, 342))`. Их длины `91-18+236-152+342-286=213` |
Вводится кортеж пар натуральных чисел. Это координаты отрезков на прямой. Рассмотрим объединение этих отрезков и найдём длину этого объединения (т. е. совокупную длину всех «закрашенных» нашими отрезками отрезков на прямой).
(66, 91), (152, 230), (21, 81), (323, 342), (158, 211), (286, 332), (294, 330), (18, 58), (183, 236)
Здесь имеются три группы накладывающихся отрезков: ((18, 58), (21, 81), (66, 91)), ((152, 230), (158, 211), (183, 236)) и ((286, 332), (294, 330), (323, 342)). Их длины 91-18+236-152+342-286=213
213
Спойлер: линейный алгоритм (точнее, с учётом использования метода .sorted(), — N logN) описан тут