Прямокутник можна повертати, тому кожен з них зручно одразу нормалізувати: запишемо його як пару , де w = \min(\text{сторін}), а h = \max(\text{сторін}). Після цього прямокутник накривається прямокутником тоді й лише тоді, коли
Тобто треба порахувати, скільки прямокутників доміновані хоча б одним іншим.
Задача розв'язується сортуванням із заміткою. Відсортуємо прямокутники за спаданням , а при рівних — за спаданням . Тепер оброблятимемо їх у цьому порядку, підтримуючи — максимальне серед уже оброблених.
Коли ми дійшли до чергового прямокутника, усі раніше оброблені мають не менше за його власне. Тому він є маленьким тоді й лише тоді, коли H \ge h. Після перевірки оновлюємо H = \max(H, h).
Порядок сортування важливий саме через рівні : додаткове впорядкування за спаданням гарантує, що серед прямокутників з однаковим спершу обробляється найвищий, і решта коректно позначаються як маленькі.
За умовою всі прямокутників різні, тому питання «прямокутник накриває сам себе» не виникає.
Складність — \mathcal{O}(N \log N), що цілком достатньо при N \le 200\,000.