OA-001. Minimum Number of Groups of Non-overlapping Rectangles

tags: OA Binary Search Greedy Longest Increasing Subsequence

Description

Given a set of n rectangles. ith rectangle has length[i] length and breadth[i] breadth.
One rectangle can overlap another rectangle, if the former has both length as well as breadth >= than the latter. We don't consider rotations of rectangles while considering overlapping.

E.g. a 3*5 rectangle can overlap 2*4 rectangle, but not a 4*2rectangle.
A 3*5 rectangle also overlaps rectangles of sizes 3*4, 2*5, as well as 3*5 (another rectangle with same dimensions)

We want to partition these rectangles into different groups, such that within each group, no rectangle can overlap another one.

What is the minimum number of groups that we can partition the rectangles into?

Constraints:
1<=n<=5000
1<=length[i], breadth[i]<=10^5

Examples:
n=5
length=[1,2,5,4,3]
breadth = [3,5,2,1,4]

Answer = 2
We can partition these rectangles into 2 groups, group 1 containing rectangles 1 and 4(1*3, 4*1), and group 2 containing rectangles 2, 3 and 5 (2*5, 5*2, 3*4)

思路

首先将所有rectangle按照length排序
排序过后 每一组rectangle的breadth都应该是降序 才能成为non-overlapping group(因为length一定是升序)
因此我们需要知道每一组最后一个加进去的rectangle的breadth
然后我们需要找到所有组最后一个breadth里面最小的但是依然大于current breadth的那一组
然后把current rectangle加到那个组里面

这就是跟LIS类似的地方
我们用一个list记录所有组的最后一个breadth
对于current breadth 我们binary search找到最小的但是大于current breadth的value
如果找得到 我们就用current breadth替换掉这个value
如果找不到 说明我们必须扩充LIS

最后LIS的长度就是答案

Code

def solution(length, breadth):
    rect = [[l, b] for l, b in zip(length, breadth)]
    rect.sort()
    increase = []
    for l, b in rect:
        # find the least value in list that is strictly bigger than b
        # if we cannot find, ans += 1
        # if we can find one, subsitute that value with b
        if len(increase)==0 or b>=increase[-1]:
            increase.append(b)
        else:
            start, end = 0, len(increase)
            while start<end:
                mid = start+(end-start)//2
                if increase[mid]<b:
                    start = mid+1
                else: end = mid
            increase[start]=b
        return len(increase)