디시인사이드 갤러리

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

갤러리 본문 영역

오늘의 릿코드 Minimum Number of Arrows~

개발뉴비갤로그로 이동합니다. 2023.01.05 23:05:19
조회 42 추천 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 - -
333 3355. Zero Array Transformation I 흑화뉴비갤로그로 이동합니다. 05.20 53 0
332 2918. Minimum Equal Sum of Two Arrays Af 흑화뉴비갤로그로 이동합니다. 05.10 21 0
331 2033. Minimum Operations to Make a Uni-V 흑화뉴비갤로그로 이동합니다. 03.28 45 0
330 2401. Longest Nice Subarray 흑화뉴비갤로그로 이동합니다. 03.19 40 0
329 1079. Letter Tile Possibilities 흑화뉴비갤로그로 이동합니다. 02.18 45 0
328 1718. Construct the Lexicographically La 흑화뉴비갤로그로 이동합니다. 02.16 29 0
327 1910. Remove All Occurrences of a Substr 흑화뉴비갤로그로 이동합니다. 02.11 31 0
326 2381. Shifting Letters II 흑화뉴비갤로그로 이동합니다. 01.05 43 0
323 2471. Minimum Number of Operations to So 흑화뉴비갤로그로 이동합니다. 24.12.25 31 0
322 773. Sliding Puzzle 흑화뉴비갤로그로 이동합니다. 24.11.27 30 0
321 3243. Shortest Distance After Road Addit 흑화뉴비갤로그로 이동합니다. 24.11.27 23 0
320 1233. Remove Sub-Folders from the Filesy 흑화뉴비갤로그로 이동합니다. 24.10.29 30 0
319 2684. Maximum Number of Moves in a Grid 흑화뉴비갤로그로 이동합니다. 24.10.29 31 0
318 2501. Longest Square Streak in an Array 흑화뉴비갤로그로 이동합니다. 24.10.29 43 0
317 3043. Find the Length of the Longest Com 흑화뉴비갤로그로 이동합니다. 24.09.24 38 0
316 1514. Path with Maximum Probability 흑화뉴비갤로그로 이동합니다. 24.08.27 38 0
315 264. Ugly Number II 흑화뉴비갤로그로 이동합니다. 24.08.19 35 0
314 2285. Maximum Total Importance of Roads 흑화뉴비갤로그로 이동합니다. 24.06.28 48 0
313 1552. Magnetic Force Between Two Balls 흑화뉴비갤로그로 이동합니다. 24.06.20 38 0
312 1482. Minimum Number of Days to Make m B 흑화뉴비갤로그로 이동합니다. 24.06.19 41 0
311 523. Continuous Subarray Sum 흑화뉴비갤로그로 이동합니다. 24.06.09 41 0
310 리트코드 갤러리 5월 이벤트 우승자 공지 [1] 진척갤로그로 이동합니다. 24.06.08 65 0
309 1208. Get Equal Substrings Within Budget 흑화뉴비갤로그로 이동합니다. 24.05.28 41 0
308 1608. Special Array With X Elements Grea 흑화뉴비갤로그로 이동합니다. 24.05.28 33 0
307 552. Student Attendance Record II 흑화뉴비갤로그로 이동합니다. 24.05.28 32 0
306 2597. The Number of Beautiful Subsets [1] 흑화뉴비갤로그로 이동합니다. 24.05.24 57 0
305 78. Subsets 흑화뉴비갤로그로 이동합니다. 24.05.21 32 0
304 1863. Sum of All Subset XOR Totals 흑화뉴비갤로그로 이동합니다. 24.05.21 36 0
302 1325. Delete Leaves With a Given Value 흑화뉴비갤로그로 이동합니다. 24.05.18 37 0
301 2331. Evaluate Boolean Binary Tree 흑화뉴비갤로그로 이동합니다. 24.05.18 28 0
298 3075. Maximize Happiness of Selected Chi 흑화뉴비갤로그로 이동합니다. 24.05.12 25 0
297 786. K-th Smallest Prime Fraction 흑화뉴비갤로그로 이동합니다. 24.05.12 29 0
296 506. Relative Ranks 흑화뉴비갤로그로 이동합니다. 24.05.08 38 0
295 2816. Double a Number Represented as a L 흑화뉴비갤로그로 이동합니다. 24.05.08 25 0
294 2487. Remove Nodes From Linked List 흑화뉴비갤로그로 이동합니다. 24.05.06 26 0
293 79. Word Search o오어o(14.37) 24.05.04 29 0
292 45. Jump Game II o오어o(14.37) 24.05.04 35 0
291 881. Boats to Save People o오어o(14.37) 24.05.04 29 0
290 2441. Largest Positive Integer That Exis 흑화뉴비갤로그로 이동합니다. 24.05.02 28 0
289 2997. Minimum Number of Operations to Ma 흑화뉴비갤로그로 이동합니다. 24.05.01 25 0
288 2000. Reverse Prefix of Word 흑화뉴비갤로그로 이동합니다. 24.05.01 34 0
287 리트코드 갤러리 5월 이벤트 공지 [3] 진척갤로그로 이동합니다. 24.04.28 97 0
282 백준 1260. DFS와 BFS 차근차근춘식이(211.234) 24.04.23 47 0
277 206. Reverse Linked List 흑화뉴비갤로그로 이동합니다. 24.03.21 48 0
276 1669. Merge In Between Linked Lists 흑화뉴비갤로그로 이동합니다. 24.03.20 30 0
275 57. Insert Interval 흑화뉴비갤로그로 이동합니다. 24.03.18 31 0
274 2485. Find the Pivot Integer 흑화뉴비갤로그로 이동합니다. 24.03.13 25 0
273 1750. Minimum Length of String After Del 흑화뉴비갤로그로 이동합니다. 24.03.06 26 0
272 451. Sort Characters By Frequency 흑화뉴비갤로그로 이동합니다. 24.02.07 40 0
271 49. Group Anagrams 흑화뉴비갤로그로 이동합니다. 24.02.06 35 0
갤러리 내부 검색
제목+내용게시물 정렬 옵션

오른쪽 컨텐츠 영역

실시간 베스트

1/8

디시미디어

디시이슈

1/2