Max number of overlapping rectangles

Question

I have seen this interview question and don't have idea on how to it: Given N rectangles, find the maximum number of overlapping rectangles. For example, for rectangles represented by bottom left and top right points, [(1, 1), (3, 3)], [(2, 2), (4, 4)], [(1, 3), (2, 4)], [(2, 2), (3, 3)], return 3 because the first two and last one rectangles overlap. I can think of an algorithm of time complexity O(n^2) but there should be an algorithm of O(NlogN).

Answer 1

This is perhaps a clearer answer

This problem can be solved in O(n^2) time complexity using the scan line algorithm. Use a scan line perpendicular to the x-axis to scan all rectangles from left to right.

Assume that the left side of rectangle i is x1 and the right side is x2i.

When the scan line meets x1, the event is entered and rectangle i is activated.

When the scan line meets x2, the event is exited, and the activation status of rectangle i is removed.

For each event, all rectangles are traversed to see which rectangles are active. The projection of those rectangles on the y-axis is then considered as an interval, and the maximum number of overlapping intervals is found by using a difference array.

The answer is found when the scan line moves to the rightmost end.

Here is a specific problem and the implemented as follows :

class Solution {
public:
  int fieldOfGreatestBlessing(vector<vector<int>>& forceField) {
    vector<pair<long long, pair<int, int>>> xevents;
    vector<int> alive(forceField.size());
    for (int i = 0; i < forceField.size(); i++) {
      auto& v = forceField[i];
      xevents.push_back(make_pair((long long)v[0] * 2 - v[2], make_pair(-1, i)));
      xevents.push_back(make_pair((long long)v[0] * 2 + v[2], make_pair(1, i)));
    }
    sort(xevents.begin(), xevents.end());
    int maxC = 0;
    for (auto& v : xevents) {
      if (v.second.first == -1) alive[v.second.second] = 1;
      else alive[v.second.second] = 0;
      vector<pair<long long, pair<int, int>>> yevents;
      for (int i = 0; i < forceField.size(); i++) {
        if (!alive[i]) continue;
        auto& v = forceField[i];
        yevents.push_back(make_pair((long long)v[1] * 2 - v[2], make_pair(-1, i)));
        yevents.push_back(make_pair((long long)v[1] * 2 + v[2], make_pair(1, i)));
      }
      if (yevents.size() == 0) {
        continue;
      }
      sort(yevents.begin(), yevents.end());
      int c = 0;
      for (auto& v : yevents) {
        if (v.second.first == -1) {
          ++c;
          if (c > maxC) {
            maxC = c;
          }
        }
        else {
          --c;
        }
      }
    }
    return maxC;
  }
};

From

Answer 2

1. Order the reactgales by 1x, y1, x2, y2
2. Then you need to go over the list, and only check if the top left coordinate of the nextrectangle lies inside one of the previous rectangles.
3. If yes > overlapping

The "formula": CR = Current rectangle to check R = Previous rectangle (add this to a loop)

cr.x1 >= r.x1 && cr.x1 < r.x2 && cr.y1 >= r.y1 && cr.y1 < r.y2

In case you are interested in .Net solution I even added extra rectangles

List<StackOverflowAnswers.Rectangle> _rectangles = new() { new() { x1 = 1, y1 = 1, x2 = 3, y2 = 3 },
new() { x1 = 2, y1 = 2, x2 = 4, y2 = 4 },
new() { x1 = 1, y1 = 3, x2 = 2, y2 = 4 },
new() { x1 = 2, y1 = 2, x2 = 3, y2 = 3 },
new() { x1 = 4, y1 = 1, x2 = 5, y2 = 2 },
new() { x1 = 1, y1 = 1, x2 = 2, y2 = 2 }
};

int _overlaps = 0;

_rectangles = _rectangles.OrderBy(r => r.x1).ThenBy(r => r.y1).ThenBy(r => r.x2).ThenBy(r => r.y2).ToList();
StackOverflowAnswers.Rectangle cr;
for (int i = 1; i<_rectangles.Count;i++)
{
    cr = _rectangles[i];
    _rectangles.GetRange(0,i).ForEach(r => _overlaps += (cr.x1 >= r.x1 && cr.x1 < r.x2 && cr.y1 >= r.y1 && cr.y1 < r.y2) ? 1:0);
}

Console.WriteLine("Overlaps: " + _overlaps);

Answer 3

In order to find the number of maximum overlaps, we need to do as follow:

• Break each rectangle into two segments, open and end, for example, for rectangle [(0,0) (1,1)] -> we can use two segments [(0,0) (0,1)] and [(1,0), (1,1)] to represent it.

• Sort all of those segments based on its x coordinate.

• Iterating through those segments, and while maintaining a segment tree to keep track of the rectangles:

  • If the segment is open and have the coordinate (x,y1) (x,y2) -> increase the segment (y1, y2) in the segment tree by one.

  • If the segment is close and have the coordinate (x,y1) (x,y2) -> decrease the segment (y1, y2) in the segment tree by one.

• When we encounter an open segment (x,y1) (x,y2), we also check how many segments are existing in (y1,y2) in the segment tree, the maximum value among those numbers are the final result.

Notice that each add/delete/search query in the segment tree is O(log n) -> we obtain an O(n log n) solution.

Answer 4

My O(N^2) algorithm is like this as requested:

1. Sort all the y-axis values of bottom and top edges with duplicates, in this example, we will get (1, 2, 2, 3, 3, 4). This step gives (NlogN) time complexity. And also for each value, we also need to record the rectangle it belongs to.

2. Get all the x-axis values of left and right edges for each rectangle (2N values for each, in this example, we will get (1, 2, 3, 4)). For each x value, we image we create a vertical line passing through (x, 0).

3. For each vertical line, iterate all the values sorted in the first step, count the maximum number of rectangles that overlapped at current vertical line. We can do it in O(N) time by sweep line algorithm (In our example, at value 1 we have 1 rectangle, then go to value 2, two rectangles added thus 3 rectangles overlapped, at value 3, one is added and the other one left, 2 rectangles overlapped). Thus in total it will give O(N^2) time complexity.