LeetCode.836.Rectangle Overlap 矩形重叠

题目描述

836 Rectangle Overlap https://leetcode-cn.com/problems/rectangle-overlap/

A rectangle is represented as a list [x1, y1, x2, y2], where (x1, y1) are the coordinates of its bottom-left corner, and (x2, y2) are the coordinates of its top-right corner.

Two rectangles overlap if the area of their intersection is positive. To be clear, two rectangles that only touch at the corner or edges do not overlap.

Given two (axis-aligned) rectangles, return whether they overlap.

Example 1:

Input: rec1 = [0,0,2,2], rec2 = [1,1,3,3]
Output: true

Example 2:

Input: rec1 = [0,0,1,1], rec2 = [1,0,2,1]
Output: false

Notes: Both rectangles rec1 and rec2 are lists of 4 integers. All coordinates in rectangles will be between -10^9 and 10^9.


相似题目

LeetCode.836.Rectangle Overlap 矩形重叠 LeetCode.056.Merge Intervals 合并重叠区间 LeetCode.452.Minimum Number of Arrows to Burst Balloons 用最少数量的箭引爆气球


解题过程

把问题分解为求区间 [left1, right1] [left2, right2] 的重叠长度,也就是 两个区间左边界的最大值和右边界的最小值之间的距离,如果左边界最大值大于右边界最小值,则不重叠。

private static class SolutionV2020 {
    // [x1, y1, x2, y2]
    public boolean isRectangleOverlap(int[] rec1, int[] rec2) {
        // x区间有重叠 且 y区间有重叠
        return overlap(rec1[0], rec1[2], rec2[0], rec2[2]) > 0 && overlap(rec1[1], rec1[3], rec2[1], rec2[3]) > 0;
    }

    // 计算区间 [left1, right1] [left2, right2] 之间的重叠长度,不重叠返回0
    private int overlap(int left1, int right1, int left2, int right2) {
        return Math.min(right1, right2) >= Math.max(left1, left2) ? Math.min(right1, right2) - Math.max(left1, left2) : 0;
    }
}

GitHub代码

algorithms/leetcode/leetcode/_836_RectangleOverlap.java https://github.com/masikkk/algorithms/blob/master/leetcode/leetcode/_836_RectangleOverlap.java