难度: Easy
原题连接
内容描述
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.
思路 1 - 时间复杂度: O(1)- 空间复杂度: O(1)******
可以从一维的overlap拓展到二维的overlap
参考lee215
Given 2 segment (left1, right1), (left2, right2), how can we check whether they overlap?
If these two intervals overlap, it should exist an number x,
left1 < x < right1 && left2 < x < right2
left1 < x < right2 && left2 < x < right1
class Solution:
def isRectangleOverlap(self, rec1, rec2):
"""
:type rec1: List[int]
:type rec2: List[int]
:rtype: bool
"""
return rec1[0] < rec2[2] and rec2[0] < rec1[2] and rec1[1] < rec2[3] and rec2[1] < rec1[3]思路 2 - 时间复杂度: O(1)- 空间复杂度: O(1)******
思考一下，我们可以算出水平线上的overlap和蔬之竖直线上的overlap，如果这两段都是正数的话那么就说明有overlap
First, separate the arrays to labeled l,b,r,t (for left, bottom, right, and top).
Then, compute how much width there is overlapping.
Basically, this is merely the horizontal distance between lesser of the right edges and greater of the left edges.
Do the same for the top and bottom to calculate the intersecting height.
Then, if both calculations are positive, there is an intersection.
beats 100%
class Solution:
def isRectangleOverlap(self, rec1, rec2):
"""
:type rec1: List[int]
:type rec2: List[int]
:rtype: bool
"""
l1, b1, r1, t1 = rec1
l2, b2, r2, t2 = rec2
width = min(r1, r2) - max(l1, l2)
height = min(t1, t2) - max(b1, b2)
return width > 0 and height > 0