Daily classic

To Li Bai by Du Fu (Tang Dynasty)

Autumn to gu is still floating peng, not on the Dan sha kui GeHong.

Drink crazy song empty spend time, flying domineering for who male.

describe

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 = 11, bursting the balloons [2,8] and [1,6]. Bursting the balloons [10,16] and [7,12].Copy the code

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.Copy the code

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 [1,2] and [2,3]. Bursting the balloons [3,4] and [4,5].Copy the code

Note:

  • 1 <= points.length <= 10^5
  • points[i].length == 2
  • -2^31 <= xstart < xend< = 2 ^ 31-1

parsing

There are some spherical balloons attached to the flat wall representing the XY plane. Balloons are represented as 2D integer array points, where points[I] = [xstart, xend] represent balloons whose diameters span xstart and xend, but the exact y-coordinates of the balloons are not required to be known.

You can shoot an arrow in the y direction along some X-axis, and if xstart <= x <= xend, the balloon within xstart and xend will be popped by the arrow. The arrow keeps moving up, popping any balloons in its path. Given an array of points, returns the minimum number of arrows that must be shot to burst all balloons.

In fact, the idea is very simple, as long as the balloons have overlapping ranges, it only needs one arrow to explode them, so the points are sorted in ascending order first, then the greedy idea is used to fuse as many balloons as possible within the range, define the left boundary mn and right boundary mx, and then traverse the points from left to right. As long as the new scope [A, B] is guaranteed! (a > mx or b < mn), indicating that the fusion can continue, otherwise, the balloon whose scope overlapped can be shot with one arrow, that is, result + 1, and then updated with new MN and mx until the end of the traversal, because in the end, one arrow is still needed, so result + 1 can be returned.

answer

class Solution(object):
    def findMinArrowShots(self, points):
        """
        :type points: List[List[int]]
        :rtype: int
        """
        points.sort()
        stack = [points[0]]
        result = 0
        mn = points[0][0]
        mx = points[0][1]
        for a, b in points[1:]:
            if a > mx or b < mn:
                result += 1
                mn = a
                mx = b
            mn = max(mn, a)
            mx = min(mx, b)
        return result+1
                
                
        
		
Copy the code

The results

Runtime: 1543 ms, faster than 31.97% of Python online submissions for Minimum Number of Arrows to Burst Balloons. Memory Usage: 61.2 MB, less than 62.08% of Python online submissions for a Minimum Number of Arrows to Burst Balloons.Copy the code

Original link: leetcode.com/problems/mi…

Your support is my biggest motivation