LeetCode 75
Minimum Number of Arrows to Burst Balloons
- Problem
- LC 452
- Topic
- Intervals
- File
- official75_LC452MinimumNumberOfArrowsToBurstBalloons.java
- Path
- pkg5leetcode/official75/official75_LC452MinimumNumberOfArrowsToBurstBalloons.java
- Package
- pkg5leetcode.official75
- Command
- java pkg5leetcode/official75/official75_LC452MinimumNumberOfArrowsToBurstBalloons.java
- Approach
- Greedy sort by end; shoot when start > last end.
- Complexity
- Time O(n log n), Space O(1)
There is no in-browser runner. This is the file from the curriculum, unchanged.
1package pkg5leetcode.official75;2 3/*4 * Minimum Number of Arrows to Burst Balloons | LC 4525 * APPROACH: Greedy sort by end; shoot when start > last end.6 * COMPLEXITY: Time O(n log n), Space O(1)7 */8import java.util.*;9 10public class official75_LC452MinimumNumberOfArrowsToBurstBalloons {11 static int findMinArrowShots(int[][] points) {12 if (points.length == 0) return 0;13 Arrays.sort(points, (a, b) -> Integer.compare(a[1], b[1]));14 int arrows = 1, end = points[0][1];15 for (int i = 1; i < points.length; i++)16 if (points[i][0] > end) { arrows++; end = points[i][1]; }17 return arrows;18 }19 20 public static void main(String[] args) {21 check(findMinArrowShots(new int[][]{{10,16},{2,8},{1,6},{7,12}}) == 2, "case1");22 check(findMinArrowShots(new int[][]{{1,2},{3,4},{5,6},{7,8}}) == 4, "case2");23 System.out.println("all tests passed");24 }25 26 static void check(boolean cond, String name) {27 if (!cond) throw new AssertionError("FAILED: " + name);28 System.out.println(" PASS " + name);29 }30}