Last Updated on 2022-01-13 by Clay
題目
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 <= 105points[i].length == 2-231 <= xstart < xend <= 231 - 1
題目給定一些氣球的水平直徑位置 [x_start, x_end]，而我們要計算如果要射穿氣球，最少可以使用多少發箭。
解題思路
這題雖然大家都說很簡單，但我卻意外地苦惱了好一段時間。主要是我一開始按照氣球的起始點進行氣球群組的排序，接著將結束點紀錄起來；下一顆氣球的起始點若在紀錄起的結束點之內，則視為可以一箭射穿的氣球......
然而我卻忽略了，我也得隨時確認擊穿氣球的最短結束點，並將其更新為紀錄起的結束點。因為我們得記得之前擊穿氣球都是用一發箭矢，如果之後遇到的氣球起始點若不在某顆氣球的結束點內，那就根本無法使用同一發箭矢擊穿。
C++ 範例程式碼
class Solution {
public:
int findMinArrowShots(vector<vector<int>>& points) {
// Base case
if (points.size() <= 1) return points.size();
// Sort
sort(points.begin(), points.end());
// Init
int arrows = 1;
int hit_range = points[0][1];
for (int i=1; i<points.size(); ++i) {
// New point out of range, we need more arrow
if (points[i][0] > hit_range) {
++arrows;
hit_range = points[i][1];
}
// If we want to hit it by an arrow, we need update the new hit range
if (points[i][1] < hit_range) hit_range = points[i][1];
}
return arrows;
}
};Python 範例程式碼
class Solution:
def findMinArrowShots(self, points: List[List[int]]) -> int:
# Base case
if len(points) <= 1: return len(points)
# Sort
points.sort()
# Init
hit_range = points[0][1]
arrows = 1
for i in range(1, len(points)):
if points[i][0] > hit_range:
arrows += 1
hit_range = points[i][1]
if points[i][1] < hit_range: hit_range = points[i][1]
return arrows