Алгоритми та структури даних · Middle · Запитання 20 з 75
Як злити інтервали, що перетинаються, наприклад [[1,3],[2,6],[8,10]]?
- 1Порівняти кожну пару інтервалів і злити ті, що перетинаються
- ✓Правильна відповідь: Відсортувати за початком і розширювати останній злитий інтервал або починати новий
- 3Відсортувати за кінцем і видалити кожен інтервал, що перетинає інший
Пояснення
Після сортування за початком інтервал перетинає попередній рівно тоді, коли його початок не пізніше за попередній кінець. Один прохід дає [[1,6],[8,10]]. Загальна вартість O(n log n) через сортування.