当前位置 : 首页 » 文章分类 :  算法  »  LeetCode.836.Rectangle Overlap 矩形重叠

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


上一篇 LeetCode.409.Longest Palindrome 最长回文串

下一篇 LeetCode.1160.Find Words That Can Be Formed by Characters 拼写单词

阅读
评论
365
阅读预计1分钟
创建日期 2020-03-18
修改日期 2020-03-18
类别

页面信息

location:
protocol:
host:
hostname:
origin:
pathname:
href:
document:
referrer:
navigator:
platform:
userAgent:

评论