contest 290 마지막 문제입니다.
You are given a 0-indexed 2D integer array flowers, where flowers[i] = [starti, endi] means the ith flower will be in full bloom from starti to endi (inclusive). You are also given a 0-indexed integer array persons of size n, where persons[i] is the time that the ith person will arrive to see the flowers.
Return an integer array answer of size n, where answer[i] is the number of flowers that are in full bloom when the ith person arrives.
# 대충 한글 요약
flowers에는 각 꽃들의 지속시간[start, end]이 나와있습니다.
밑에 그림 보시면 바로 이해 되실껍니다.
Example 1
Input: flowers = [[1,6],[3,7],[9,12],[4,13]], persons = [2,3,7,11]
Output: [1,2,2,2]
Example 2
Input: flowers = [[1,10],[3,3]], persons = [3,3,2]
Output: [2,2,1]
제한사항
이 문제도 역시 제한조건이 빡셉니다.
사람은 문제 없어보이는데 꽃이 지속되는 최대 길이가 1,000,000,000 - 1
class Solution:
def fullBloomFlowers(self, flowers: List[List[int]], persons: List[int]) -> List[int]:
start, end = [] , []
for s, e in flowers:
start.append(s)
end.append(e)
start.sort()
end.sort()
return [bisect_right(start, p) - bisect_left(end, p) for p in persons ]
이진탐색을 응용해서 범위별로 탐색할 수 있는 기법입니다.