Максимальная точка перекрытия прямоугольника

Учитывая координаты N прямоугольников (N <= 100.000) в сетке L * C (L и C может варьироваться от 0 до 1.000.000.000), я хочу знать, каково максимальное количество перекрывающихся прямоугольников в любой точке сетка.

Итак, я решил, что буду использовать алгоритм подметания для каждого события (открытия или окончания прямоугольника), отсортированного по значению x, я добавляю или удаляю интервал в мою структуру.

Мне нужно использовать дерево, чтобы поддерживать максимальное перекрытие интервалов и иметь возможность добавлять и удалять интервал.

Я знаю, как это сделать, когда значения интервалов (начало и конец) находятся в диапазоне от 0 до 100 000, но здесь невозможно, так как размеры плоскости составляют от 0 до 1.000.000.000. Как я могу реализовать такое дерево?

2 ответа

Если вы знаете координаты всех прямоугольников вверх, вы можете использовать "сжатие координат".

Поскольку у вас есть только 10 ^ 5 прямоугольников, это означает, что у вас есть не более 2 * 10 ^ 5 разных координат x и y. Поэтому вы можете создать отображение из этих координат в натуральные числа от 1 до 2 * 10 ^ 5 (просто отсортировав координаты). Затем вы можете просто использовать обычное дерево, которое вы уже знаете для новых координат.

Этого было бы достаточно, чтобы получить количество прямоугольников, но если вам также нужна точка, где они перекрываются, вы также должны поддерживать обратное сопоставление, чтобы вернуться к реальным координатам прямоугольников. В общем случае ответом будет прямоугольник, а не только одна точка.


Используйте дерево интервалов . Ваш случай немного сложнее, потому что вам действительно нужно взвешенное дерево интервалов, где вес - это количество открытых прямоугольников для этого интервала.

licensed under cc by-sa 3.0 with attribution.