У кожній парі одна кімната цілком передує іншій. Тому розбиття — це поділ кімнат на «ранніх» і «пізніх» так, щоб -й за зростанням правий кінець серед ранніх не перевищував -го за зростанням лівого кінця серед пізніх.
Це зручно перевіряти розгорткою коридору зліва направо. Кімната, яка закінчилася й нікого не обслуговує, дає одиницю покриття; кімната, яку ми оголошуємо пізньою в момент її початку, витрачає одиницю покриття. Умова означає рівно те, що покриття ніколи не стає від'ємним.
Жадібно оголошуємо кожну кімнату, що починається, пізньою, якщо покриття є. Якщо покриття немає, візьмемо вже оголошену пізньою кімнату з найменшим правим кінцем і скасуємо її оголошення на користь поточної. Це коректно: скасування повертає витрачену одиницю й додає власне покриття цієї кімнати, а нове оголошення припадає на пізніший лівий кінець, тож жодна раніша точка не постраждала, а кількість пар не змінилася. Саме ця заміна робить жадібне оголошення безпечним — без неї кімната, оголошена пізньою зарано, з'їдає покриття, потрібне справді безвихідній кімнаті.
Відповідь — possible тоді й лише тоді, коли пар набралося рівно . Оголошені кімнати зберігаються в купі за правим кінцем.
Складність: O(n \log n) на набір даних.
Для цього етапу офіційного розбору опубліковано не було; цей текст написано для архіву за розв'язком, який перевірено на задачі.