Rectangle Area

https://leetcode.com/problems/rectangle-area/description/

Find the total area covered by tworectilinearrectangles in a2Dplane.

Each rectangle is defined by its bottom left corner and top right corner as shown in the figure.

Thoughts

要算出overlapping的面积, 一种是分类讨论, A是在E左边还是右边啊等等非常麻烦. 但实际上我们并不需要真的关心具体是那种情况, 只要知道overlapping rectangle的长和宽是多少即可. overlapping的出现是因为左边方块的最右边比右边方块的最左边大, 因此我们只要检查下最靠左的右测边(right)是不是大于最靠右的左侧边(left), 上下边同理. 因此为了知道宽是多少, 我们需要找出左边方块的右侧边右边方块的左侧边等等.

Code

class Solution {
    public int computeArea(int A, int B, int C, int D, int E, int F, int G, int H) {
        int overlapping = 0;
        int left = Math.max(A, E), right = Math.min(C, G);
        int bottom = Math.max(B, F), top = Math.min(D, H);
        if (right > left && top > bottom) {
            overlapping = (right - left) * (top - bottom);
        }

        return (C - A) * (D - B) + (G - E) * (H - F) - overlapping;
    }
}

Analysis

时空复杂度O(1).