디시인사이드 갤러리

마이너 갤러리 이슈박스, 최근방문 갤러리

갤러리 본문 영역

오늘의 릿코드 Minimum Number of Arrows~

개발뉴비갤로그로 이동합니다. 2023.01.05 23:05:19
조회 40 추천 0 댓글 0
														

https://leetcode.com/problems/minimum-number-of-arrows-to-burst-balloons/

 

Minimum Number of Arrows to Burst Balloons - LeetCode

Minimum Number of Arrows to Burst Balloons - There are some spherical balloons taped onto a flat wall that represents the XY-plane. The balloons are represented as a 2D integer array points where points[i] = [xstart, xend] denotes a balloon whose horizontal diameter stretches between xstart and xend. You do not know the exact y-coordinates of the balloons. Arrows can be shot up directly vertically (in the positive y-direction) from different points along the x-axis. A balloon with xstart and xend is burst by an arrow shot at x if xstart <= x <= xend. There is no limit to the number of arrows that can be shot. A shot arrow keeps traveling up infinitely, bursting any balloons in its path. Given the array points, return the minimum number of arrows that must be shot to burst all balloons.   Example 1: Input: points = [[10,16],[2,8],[1,6],[7,12]] Output: 2 Explanation: The balloons can be burst by 2 arrows: - Shoot an arrow at x = 6, bursting the balloons [2,8] and [1,6]. - Shoot an arrow at x = 11, bursting the balloons [10,16] and [7,12]. Example 2: Input: points = [[1,2],[3,4],[5,6],[7,8]] Output: 4 Explanation: One arrow needs to be shot for each balloon for a total of 4 arrows. Example 3: Input: points = [[1,2],[2,3],[3,4],[4,5]] Output: 2 Explanation: The balloons can be burst by 2 arrows: - Shoot an arrow at x = 2, bursting the balloons [1,2] and [2,3]. - Shoot an arrow at x = 4, bursting the balloons [3,4] and [4,5].   Constraints: * 1 <= points.length <= 105 * points[i].length == 2 * -231 <= xstart < xend <= 231 - 1

leetcode.com


class Solution:
    def findMinArrowShots(self, points: List[List[int]]) -> int:
        points.sort()
        ans, cur, cut = 0, points[0][0], points[0][1]
        for start, end in points:
            if start <= min(cut, end) :
                cur, cut = start, min(cut, end)
            else :
                cur, cut, ans = cut+1, end, ans+1

        return ans + 1


귀찮으니까 그냥 O(N)으로 긁도록 하겠습니다. 

점들을 계속 받으면서 가장 일찍 끝나는 녀석보다 늦게 시작하는 놈이 나오면 화살 쏴야됨.


추천 비추천

0

고정닉 0

0

댓글 영역

전체 댓글 0
본문 보기

하단 갤러리 리스트 영역

왼쪽 컨텐츠 영역

갤러리 리스트 영역

갤러리 리스트
번호 제목 글쓴이 작성일 조회 추천
설문 2025년 가장 기억에 남는 인터넷 이슈는? 운영자 25/12/22 - -
86 909. Snakes and Ladders [1] 개발뉴비갤로그로 이동합니다. 23.01.24 54 0
85 909. Snakes and Ladders 이벤트ㅇㅅㅇ(219.251) 23.01.24 47 0
83 997. Find the Town Judge 이벤트ㅇㅅㅇ(219.251) 23.01.23 44 0
82 997. Find the Town Judge [1] 개발뉴비갤로그로 이동합니다. 23.01.23 74 0
81 백준 9996번 키비갤로그로 이동합니다. 23.01.23 56 0
78 마갤 입문함 [2] 키비갤로그로 이동합니다. 23.01.22 59 0
77 131. Palindrome Partitioning [1] 개발뉴비갤로그로 이동합니다. 23.01.22 57 0
75 93. Restore IP Addresses [1] 개발뉴비갤로그로 이동합니다. 23.01.21 72 0
74 Longest Palindromic Substring 5번 o오어o(14.37) 23.01.21 30 0
73 Restore IP Addresses 93번 o오어o(14.37) 23.01.21 38 0
72 안녕하세요 오늘부터 릿코 달리게씁니당 [2] 조르디(112.170) 23.01.21 53 0
71 491. Non-decreasing Subsequences [1] 개발뉴비갤로그로 이동합니다. 23.01.21 56 0
70 974. Subarray Sums Divisible by K [1] 개발뉴비갤로그로 이동합니다. 23.01.19 43 0
69 926. Flip String to Monotone Increasing [1] 개발뉴비갤로그로 이동합니다. 23.01.17 41 0
68 57. Insert Interval [1] 개발뉴비갤로그로 이동합니다. 23.01.17 37 0
66 트리 문제 두 개 개빡치네; 개발뉴비갤로그로 이동합니다. 23.01.15 48 0
65 1061. Lexicographically Smallest ~ 개발뉴비갤로그로 이동합니다. 23.01.15 42 0
64 여기 갤럼들은 전부 해외취업 준비중? [2] EvenAsura갤로그로 이동합니다. 23.01.14 105 0
63 1519. Number of Nodes in the Sub-Tree~ 개발뉴비갤로그로 이동합니다. 23.01.12 28 0
62 1443. Minimum Time to Collect All Apples 개발뉴비갤로그로 이동합니다. 23.01.11 40 0
59 230111 데일리 꽃지갤로그로 이동합니다. 23.01.11 68 0
58 100. Same Tree 개발뉴비갤로그로 이동합니다. 23.01.10 34 0
56 220110 데일리 꽃지갤로그로 이동합니다. 23.01.10 40 0
53 144. Binary Tree Preorder Traversal 개발뉴비갤로그로 이동합니다. 23.01.09 40 0
52 230109 데일리 꽃지갤로그로 이동합니다. 23.01.09 31 0
51 리트코드 4번 [4] o오어o(222.121) 23.01.09 65 0
50 리트코드 3번 o오어o(222.121) 23.01.09 25 0
49 220108 데일리 꽃지갤로그로 이동합니다. 23.01.08 54 0
48 68. Text Justification ㅇㅇ(12.50) 23.01.08 35 0
47 3번문제 코드 딱 한줄만 알려준다 ㅇㅇ(218.234) 23.01.08 37 0
46 코딩 테스트 tdd로 하시는 분 [1] TS(119.64) 23.01.07 61 0
45 가스스테이션(데일리) o오어o(222.121) 23.01.07 51 0
44 230107 데일리 [1] 꽃지갤로그로 이동합니다. 23.01.07 55 0
43 134. Gas Station 개발뉴비갤로그로 이동합니다. 23.01.07 47 0
42 1833. Maximum Ice Cream Bars 개발뉴비갤로그로 이동합니다. 23.01.06 58 0
41 230106 데일리 꽃지갤로그로 이동합니다. 23.01.06 50 0
오늘의 릿코드 Minimum Number of Arrows~ 개발뉴비갤로그로 이동합니다. 23.01.05 40 0
36 230105 데일리 [3] 꽃지갤로그로 이동합니다. 23.01.05 65 0
35 2244. Minimum Rounds 이거 푸는데 TS(119.64) 23.01.05 36 0
34 데일리 문제 어떻게 알아봄...? [1] TS(119.64) 23.01.05 40 0
33 230104 데일리 [2] 꽃지갤로그로 이동합니다. 23.01.04 86 0
31 Minimum Rounds to Complete All Task [1] 개발뉴비갤로그로 이동합니다. 23.01.04 102 0
30 944. Delete Columns to Make Sorted in TS ㅇㅇ(119.64) 23.01.04 43 0
29 백준 17726 Inheritance 꽃지갤로그로 이동합니다. 23.01.04 57 0
28 백준 14503번 로봇 청소기 개발뉴비갤로그로 이동합니다. 23.01.04 93 0
23 오늘의 릿코드 Delete Columns to Make Sorted [2] 개발뉴비갤로그로 이동합니다. 23.01.03 78 0
22 오늘의 데일리 [3] 꽃지갤로그로 이동합니다. 23.01.03 83 0
19 리트코드 해보면서 느낀 점 ㅇㅇ(119.64) 23.01.03 90 0
18 어쨌든 TS로 대문자 판별하기 문제 풀었는데 ㅇㅇ(119.64) 23.01.03 47 0
17 저는 js로 할게요 [5] ㅇㅇ(119.64) 23.01.03 80 0
갤러리 내부 검색
제목+내용게시물 정렬 옵션

오른쪽 컨텐츠 영역

실시간 베스트

1/8

디시미디어

디시이슈

1/2