만발한 꽃의 수

인덱스가 0인 2D 정수 배열flowers이 주어집니다. 여기서 flowers[i] = [starti, endi]는 ith 꽃이 starti에서 endi(포함)까지 만발함을 의미합니다. 또한 persons 크기의 0 인덱스 정수 배열n이 제공됩니다. 여기서 persons[i]는 ith 사람이 꽃을 보러 도착하는 시간입니다.
answer 크기의 정수 배열 n을 반환합니다. 여기서 answer[i]는 ith명의 사람이 도착했을 때 만개한 꽃의 수입니다.

예 1:



입력: 꽃 = [[1,6],[3,7],[9,12],[4,13]], 사람 = [2,3,7,11]
출력: [1,2,2,2]
설명 : 위의 그림은 꽃이 만발한 시간과 사람들이 도착하는 시간을 보여줍니다.
1인당 도착 시 만개한 꽃의 수를 반환합니다.

예 2:



입력: 꽃 = [[1,10],[3,3]], 사람 = [3,3,2]
출력: [2,2,1]
설명 : 위의 그림은 꽃이 만발한 시간과 사람들이 도착하는 시간을 보여줍니다.
1인당 도착 시 만개한 꽃의 수를 반환합니다.

제약:

1 <= flowers.length <= 5 * 104

flowers[i].length == 2

1 <= starti <= endi <= 109

1 <= persons.length <= 5 * 104

1 <= persons[i] <= 109

해결책:

from collections import defaultdict
import bisect

class Solution:
    def fullBloomFlowers(self, flowers: List[List[int]], persons: List[int]) -> List[int]:
        times = defaultdict(int)
        for s, e in flowers:
            times[s] += 1
            times[e + 1] -= 1
        timekeys = sorted(times.keys())
        prefix = [0]
        for t in timekeys:
            prefix.append(prefix[-1] + times[t])
        answer = []
        for p in persons:
            i = bisect.bisect_right(timekeys, p)
            answer.append(prefix[min(i, len(prefix) - 1)])
        return answer