LeetCode Solutions

			

struct Event {
  int x;
  int y1;
  int y2;
  char type;
  Event(int x, int y1, int y2, char type) : x(x), y1(y1), y2(y2), type(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');
    }

    sort(begin(events), end(events),
         [](const auto& a, const auto& b) { return a.x < b.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);
        sort(begin(yPairs), end(yPairs));
      } else {  // Type == 'e'
        const auto it =
            find(begin(yPairs), end(yPairs), 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;
  }
};

			

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) -> 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;
  }
}

			

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)