Максимальное количество перекрывающихся прямоугольников хотя бы с одной общей точкой

Даны четыре массива x1[] , x2[] , y1[] , y2[] размера N , где ( x1[i] , y1[i] ) обозначает левый нижний угол и ( x2[i] , y2[i] ) правый верхний угол прямоугольника, задача состоит в том, чтобы найти максимальное количество перекрывающихся прямоугольников, имеющих хотя бы одну общую точку.

Примеры:

Input: N = 2 x1[] = {0, 50} y1[] = {0, 50} x2[] = {100, 60} y2[] = {100, 60}
Output: 2
Explanation: There are two rectangles {{0, 0}, {100, 100}}, {{50, 50}, {60, 60}} and both of them are intersecting as shown in the given figure below:

Input: N = 2 x1[] = {0, 100} y1[] = {0, 100} x2[] = {100, 200} y2[] = {100, 200}
Output: 1

Подход: данная проблема может быть решена с помощью жадного подхода, который основан на идее, что каждый прямоугольник на координатной плоскости имеет свою собственную область, и когда несколько прямоугольников добавляются на одной плоскости, они создают пересечения друг с другом. Поэтому, чтобы выбрать максимальное количество прямоугольников, перекрывающихся на общей области, жадно выберите область размером 1×1, так как все перекрывающиеся области будут иметь как минимум столько блоков. Выполните следующие шаги, чтобы решить данную проблему:

• Так как есть N прямоугольников, и каждый прямоугольник имеет 2 координаты X и 2 координаты Y. Всего будет 2*N координат X и Y-координат .
• Поэтому создайте вектор координат X и Y и вытолкните все X и Y из прямоугольников в соответствующих векторах.
• Инициализируйте переменную, скажем, maxRectangles как 0 , которая хранит максимальное количество перекрывающихся прямоугольников.
• Пройдите вектор X[] и для каждой координаты X[i] пройдите вектор Y[] и найдите количество перекрывающихся прямоугольников с X[i] и после этого шага обновите значение maxRectangles до максимума maxRectangles и подсчитайте полученное за текущую итерацию.
• После выполнения вышеуказанных шагов выведите в качестве результата значение maxRectangles .

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O(N ³ )
Вспомогательное пространство: O(N)