Skip to content

850. Rectangle Area II 👍

  • Time: $O(n^2\log n)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
struct Event {
  int x;
  int y1;
  int y2;
  char type;
};

class Solution {
 public:
  int rectangleArea(vector<vector<int>>& rectangles) {
    constexpr int kMod = 1'000'000'007;

    vector<Event> events;

    for (const vector<int>& r : rectangles) {
      events.emplace_back(r[0], r[1], r[3], 's');
      events.emplace_back(r[2], r[1], r[3], 'e');
    }

    ranges::sort(events, ranges::less{},
                 [](const Event& event) { return event.x; });

    long ans = 0;
    int prevX = 0;
    vector<pair<int, int>> yPairs;

    for (const auto& [currX, y1, y2, type] : events) {
      if (currX > prevX) {
        const int width = currX - prevX;
        ans = (ans + width * getHeight(yPairs)) % kMod;
        prevX = currX;
      }
      if (type == 's') {
        yPairs.emplace_back(y1, y2);
        ranges::sort(yPairs);
      } else {  // type == 'e'
        const auto it =
            find(yPairs.begin(), yPairs.end(), pair<int, int>(y1, y2));
        yPairs.erase(it);
      }
    }

    return ans % kMod;
  }

 private:
  long getHeight(const vector<pair<int, int>>& yPairs) {
    int height = 0;
    int prevY = 0;

    for (const auto& [y1, y2] : yPairs) {
      prevY = max(prevY, y1);
      if (y2 > prevY) {
        height += y2 - prevY;
        prevY = y2;
      }
    }

    return height;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
class Event {
  public int x;
  public int y1;
  public int y2;
  public char type;
  public Event(int x, int y1, int y2, char type) {
    this.x = x;
    this.y1 = y1;
    this.y2 = y2;
    this.type = type;
  }
}

class Solution {
  public int rectangleArea(int[][] rectangles) {
    final int kMod = 1_000_000_007;
    List<Event> events = new ArrayList<>();

    for (int[] r : rectangles) {
      events.add(new Event(r[0], r[1], r[3], 's'));
      events.add(new Event(r[2], r[1], r[3], 'e'));
    }

    Collections.sort(events, (a, b) -> Integer.compare(a.x, b.x));

    long ans = 0;
    int prevX = 0;
    List<Pair<Integer, Integer>> yPairs = new ArrayList<>();

    for (Event e : events) {
      if (e.x > prevX) {
        final int width = e.x - prevX;
        ans = (ans + width * getHeight(yPairs)) % kMod;
        prevX = e.x;
      }
      if (e.type == 's') {
        yPairs.add(new Pair<>(e.y1, e.y2));
        Collections.sort(yPairs, Comparator.comparing(Pair::getKey));
      } else { // type == 'e'
        yPairs.remove(new Pair<>(e.y1, e.y2));
      }
    }

    return (int) (ans % kMod);
  }

  private long getHeight(List<Pair<Integer, Integer>> yPairs) {
    int height = 0;
    int prevY = 0;

    for (Pair<Integer, Integer> pair : yPairs) {
      final int y1 = pair.getKey();
      final int y2 = pair.getValue();
      prevY = Math.max(prevY, y1);
      if (y2 > prevY) {
        height += y2 - prevY;
        prevY = y2;
      }
    }

    return height;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution:
  def rectangleArea(self, rectangles: list[list[int]]) -> int:
    events = []

    for x1, y1, x2, y2 in rectangles:
      events.append((x1, y1, y2, 's'))
      events.append((x2, y1, y2, 'e'))

    events.sort(key=lambda x: x[0])

    ans = 0
    prevX = 0
    yPairs = []

    def getHeight(yPairs: list[tuple[int, int]]) -> int:
      height = 0
      prevY = 0

      for y1, y2 in yPairs:
        prevY = max(prevY, y1)
        if y2 > prevY:
          height += y2 - prevY
          prevY = y2

      return height

    for currX, y1, y2, type in events:
      if currX > prevX:
        width = currX - prevX
        ans += width * getHeight(yPairs)
        prevX = currX
      if type == 's':
        yPairs.append((y1, y2))
        yPairs.sort()
      else:  # type == 'e'
        yPairs.remove((y1, y2))

    return ans % (10**9 + 7)