Задача 9 дня Advent of Code — Disk Fragmenter.
😊 Часть I. Описание задачи
На диске из N секторов хранятся файлы, каждый занимая непрерывный блок секторов. Между блоками могут быть «пробелы» (свободные сектора).
- Задача: последовательно перемещать по одному сектору каждого файла (начиная с конца списка) в самый левый доступный свободный сектор, пока не исчезнут все разрывы.
- Пример:
В начале: 00...111...2...333.44.5555.6666.777.888899После: 0099811188827773336446555566..............
😊 Часть II. Описание задачи
Теперь вместо по-секторного перемещения перемещаем файлы целиком, один раз для каждого файла, в порядке убывания file_id. Для каждого файла (перебираем справа-налево) ищем самый левый свободный диапазон длины ≥ размера файла;
если он находится левее текущего — перемещаем файл, иначе оставляем на месте.
- Пример:
В начале: 00...111...2...333.44.5555.6666.777.888899После: 00992111777.44.333....5555.6666.....8888..
💡 Идея решения
Строим дерево отрезков над массивом из N секторов.
Читать дальше →