Greedy, Python (132 ms)


  • 20
    C
    1. Sort intervals by ending value;
    2. Only count valid intervals we need, and skip overlapping intervals
      return the count
    class Solution(object):
        def findMinArrowShots(self, points):
            """
            :type points: List[List[int]]
            :rtype: int
            """
            points = sorted(points, key = lambda x: x[1])
            res, end = 0, -float('inf')
            for interval in points:
                if interval[0] > end:
                    res += 1
                    end = interval[1]
            return res
    

  • 0
    Z

    The idea is concise and awesome!
    I also use greedy and Python to solve this problem, I think my solution is somewhat like yours. But there is some different in terms of the way to group the balloons. And mine is wrong. Would you please look my solution for me to find the mistake? It will be my pleasure if you have time to do this for me. The link is https://discuss.leetcode.com/topic/67792/why-my-solution-is-wrong-use-python


  • 3
    R

    Your "dict" representation of intervals is problematic, because when multiple intervals have same ending time, only one interval will be kept.

    For example: if input is [1, 2], [4, 5], [1,5], your dictionary will be points_dic[2] = 1, and points_dic[5] = 1. [4,5] is discarded!

    The correct solution is 2, but your algorithm will give 1.


  • 0
    Z

    @readerguo Oh! I see it!!!! Thank you very very very much!!! Want to LIKE you a hundred times if I can!!!!!


  • 1

    Very straightforward! I overthink but actually the only thing changed in this problem is the overlapping definition.
    Here is the Java version of your solution. Thanks a lot!

        // All considered as overlapping, so there must exist a vertical line bursting all of them:
        // [-----]
        //    [----]
        //   [----]
        //       [---]
        //  [-][-]    impossible earlier finish time!
        public int findMinArrowShots(int[][] points) {
            Arrays.sort(points, Comparator.comparingInt(p -> p[1]));
            long max = 0, last = Long.MIN_VALUE;
            for (int[] p : points) {
                if (last < p[0]) { // an arrow shot at x if xstart ≤ x ≤ xend
                    last = p[1];
                    max++;
                }
            }
            return (int) max;
        }
    

  • 0

    The same but I sort on Xstart.

    def findMinArrowShots(self, points):
            ret, shoot = 0, float('inf')
            for s, e in sorted(points, reverse=True):
                if shoot > e:
                    shoot = s
                    ret += 1
            return ret

  • 0
    O

    Brilliant solution!


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.