391. Perfect Rectangle #

Problem #

Given an array rectangles where rectangles[i] = [xi, yi, ai, bi] represents an axis-aligned rectangle. The bottom-left point of the rectangle is (xi, yi) and the top-right point of it is (ai, bi).

Return true if all the rectangles together form an exact cover of a rectangular region.

Example1:

Input: rectangles = [[1,1,3,3],[3,1,4,2],[3,2,4,4],[1,3,2,4],[2,3,3,4]]
Output: true
Explanation: All 5 rectangles together form an exact cover of a rectangular region.

Example2:

Input: rectangles = [[1,1,2,3],[1,3,2,4],[3,1,4,2],[3,2,4,4]]
Output: false
Explanation: Because there is a gap between the two rectangular regions.

Example3:

Input: rectangles = [[1,1,3,3],[3,1,4,2],[1,3,2,4],[3,2,4,4]]
Output: false
Explanation: Because there is a gap in the top center.

Example4:

Input: rectangles = [[1,1,3,3],[3,1,4,2],[1,3,2,4],[2,2,4,4]]
Output: false
Explanation: Because two of the rectangles overlap with each other.

Constraints:

• 1 <= rectangles.length <= 2 * 10000
• rectangles[i].length == 4
• -100000 <= xi, yi, ai, bi <= 100000

Problem Summary #

Given an array rectangles, where rectangles[i] = [xi, yi, ai, bi] represents an axis-aligned rectangle. The bottom-left vertex of this rectangle is (xi, yi), and the top-right vertex is (ai, bi).

If all the rectangles together exactly cover a certain rectangular region, return true; otherwise, return false.

Solution Approach #

• If the area of the rectangular region equals the sum of the areas of all rectangles, and the four corner vertices of the rectangular region each appear exactly once, while all other vertices appear only two or four times, then return true; otherwise, return false.

Code #

package leetcode

type point struct {
	x int
	y int
}

func isRectangleCover(rectangles [][]int) bool {
	minX, minY, maxA, maxB := rectangles[0][0], rectangles[0][1], rectangles[0][2], rectangles[0][3]
	area := 0
	cnt := make(map[point]int)
	for _, v := range rectangles {
		x, y, a, b := v[0], v[1], v[2], v[3]
		area += (a - x) * (b - y)
		minX = min(minX, x)
		minY = min(minY, y)
		maxA = max(maxA, a)
		maxB = max(maxB, b)
		cnt[point{x, y}]++
		cnt[point{a, b}]++
		cnt[point{x, b}]++
		cnt[point{a, y}]++
	}
	if area != (maxA - minX) * (maxB - minY) ||
		cnt[point{minX, minY}] != 1 || cnt[point{maxA, maxB}] != 1 ||
		cnt[point{minX, maxB}] != 1 || cnt[point{maxA, minY}] != 1 {
		return false
	}
	delete(cnt, point{minX, minY})
	delete(cnt, point{maxA, maxB})
	delete(cnt, point{minX, maxB})
	delete(cnt, point{maxA, minY})
	for _, v := range cnt {
		if v != 2 && v != 4 {
			return false
		}
	}
	return true
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}