391.完美矩形

链接：391.完美矩形
难度：Hard
标签：数组、扫描线
简介：如果所有矩形一起精确覆盖了某个矩形区域，则返回 true ；否则，返回 false 。

题解 1 - typescript

• 编辑时间：2021-11-16
• 执行用时：272ms
• 内存消耗：62.8MB
• 编程语言：typescript
• 解法介绍：计数判断面积和顶点重合次数。

function isRectangleCover(rectangles: number[][]): boolean {
  /**
           完美矩形要满足:
           1. 最左上、左下、右上、右下四个顶点只出现1次;
           2. 重合顶点重合次数必须为2、4，不能出现一次。
           3. 大矩形面积等于小矩形面积之和。
           */
  type Data = { cnt: number; point: number[] };
  const set = new Set<string>();
  const map: Record<string, Data> = {};
  const format = (x: number, y: number) => `${x}:${y}`;
  const map_add = (x: number, y: number) => {
    const formatStr = format(x, y);
    let data = map[formatStr];
    if (!data) map[formatStr] = data = { cnt: 0, point: [x, y] };
    data.cnt++;
  };
  let sum = 0;
  const vertex: number[] = [];
  const is_vertex = (x: number, y: number) =>
    (x === vertex[0] && y === vertex[1]) ||
    (x === vertex[2] && y === vertex[3]) ||
    (x === vertex[0] && y === vertex[3]) ||
    (x === vertex[2] && y === vertex[1]);
  for (const [x, y, a, b] of rectangles) {
    const formatStr = format(x, y) + ':' + format(a, b);
    if (set.has(formatStr)) return false;
    set.add(formatStr);
    if (vertex[0] === undefined || vertex[0] > x || vertex[1] > y) {
      vertex[0] = x;
      vertex[1] = y;
    }
    if (vertex[2] === undefined || vertex[2] < a || vertex[3] < b) {
      vertex[2] = a;
      vertex[3] = b;
    }
    sum += (a - x) * (b - y);
    map_add(x, y);
    map_add(a, b);
    map_add(x, b);
    map_add(a, y);
  }
  if ((vertex[2] - vertex[0]) * (vertex[3] - vertex[1]) !== sum) return false;
  for (const {
    cnt,
    point: [x, y],
  } of Object.values(map)) {
    if ((cnt === 1 && !is_vertex(x, y)) || (cnt !== 1 && cnt !== 2 && cnt !== 4)) {
      return false;
    }
  }
  return true;
}