[2251] Number of Flowers in Full Bloom | Hard | contest 290

yoongyum·2022년 4월 26일
0

코딩테스트 🧩

목록 보기
21/47
post-thumbnail

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]

제한사항

  • 1flowers.length51041 ≤ flowers.length ≤ 5 * 10^4
  • flowers[i].length==2flowers[i].length == 2
  • 1startiendi1091 ≤ starti ≤ endi ≤ 10^9
  • 1persons.length51041 ≤ persons.length ≤ 5 * 10^4
  • 1persons[i]1091 ≤ persons[i] ≤ 10^9

이 문제도 역시 제한조건이 빡셉니다.
사람은 문제 없어보이는데 꽃이 지속되는 최대 길이가 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 ]

이진탐색을 응용해서 범위별로 탐색할 수 있는 기법입니다.

0개의 댓글