Learning Outcome
After this lesson, you should be able to group overlapping intervals by shooting at the earliest possible end.
Problem Statement
Given balloon intervals, return the minimum number of arrows needed to burst all balloons.
| Input | Output | Why |
|---|---|---|
points = [[10,16],[2,8],[1,6],[7,12]] | 2 | One arrow can burst [1,6] and [2,8], and another can burst [7,12] and [10,16]. |
Brute Force Approach
Try many possible arrow positions and test which balloons they burst. This is unnecessary.
Optimized Approach
Sort by end. Shoot an arrow at the current earliest end, and start a new arrow only when the next interval starts after that end.
Exact Pseudocode
sort points by end
arrows = 0
arrowEnd = -infinity
for point in points:
if point.start > arrowEnd:
arrows += 1
arrowEnd = point.end
return arrowsReference Code
class Solution:
def findMinArrowShots(self, points):
points.sort(key=lambda x: x[1])
arrows = 0
arrow_end = float("-inf")
for start, end in points:
if start > arrow_end:
arrows += 1
arrow_end = end
return arrowsSample Dry Run
| Step | State | Result |
|---|---|---|
| Sort by end | [1,6], [2,8], [7,12], [10,16] | Earliest end first |
| First arrow | Shoot at 6 | Bursts [1,6] and [2,8] |
| Next start 7 | 7 > 6 | Need second arrow at 12 |
| [10,16] | 10 <= 12 | Same second arrow works |
Complexity
| Measure | Value | Reason |
|---|---|---|
| Time | O(n log n) | Sorting dominates the runtime. |
| Space | O(1) | Only arrow count and current arrow end are stored. |
Edge Cases
- Intervals sharing an endpoint can be burst by the same arrow.
- An empty list returns 0.
- Use strict start > arrowEnd to start a new arrow.
Interview Checklist
- Sort by end coordinate.
- Shoot at the earliest end of the current group.
- Start a new arrow only when the next start is greater than arrowEnd.
FAQs
Why shoot at the end?
The earliest end keeps the arrow inside the current balloon while maximizing chance to hit future balloons.
Why use > and not >=?
If a balloon starts exactly at arrowEnd, the arrow at that coordinate still bursts it.
What is the core pattern?
Interval-end greedy grouping.