九章演算法 | Facebook面試題：用最少的箭刺破所有氣球

撰文 | JZ

專欄 | 九章演算法

題目描述

在二維空間中的一組氣球，給出每個氣球的橫向直徑的起始橫坐標和結束橫坐標，保證起始橫坐標小於結束橫坐標。不需要考慮氣球的縱坐標，因此橫坐標區間可以相互重疊。氣球最多有10000個。一支箭可以選定一個橫坐標縱向射擊。一個氣球的橫向直徑兩端橫坐標為xbegin,xend，一支箭射擊的橫坐標為x，如果有xbegin<=x<=xend，則這支箭可以刺破該氣球。沒有箭的使用數量限制，並且一支箭可以刺破相應坐標上的所有氣球。

求出刺破所有氣球所需的最少的箭的數量。

樣例

輸入: [[10,16], [2,8], [1,6], [7,12]]輸出: 2說明:一種方案是在坐標x=6射一支箭（可以刺破氣球[2,8]和[1,6]），在坐標x=11射另一隻箭（刺破剩下的兩個氣球）

解題思路分析

a. 考慮n個區間[s(i), f(i)]，i=1,2,……,n，表示n個氣球的橫向直徑的左右端點所表示的區間。如果它們全都互相重疊，那麼就可以在它們的相交區間上取一點射箭，這支箭即可刺破所有氣球。如果存在互不重疊的區間，那麼為了將這些區間的氣球刺破，就不得不在這些區間中各射一支箭。

假設區間右端點坐標f(1),f(2),……,f(n)，已按從小到大排序，對於這類在一個軸上的區間問題，我們常用的思路是按照左（右）端點排序。考慮第一個區間（右端點坐標f(1)最小的區間），至少要用一支箭將該區間的氣球刺破，那麼這支箭射在什麼位置可以使它刺破儘可能多的氣球呢？

答案是區間的右端點坐標。事實上，對於射在任何坐標x<f(1)上的箭能刺破的氣球，射在f(1)上一定能刺破，因為f(1)是所有右端點中最小的，在x上能刺破的氣球右端點也不會小於f(1)。

這樣我們就得到了一個貪心的策略：先按區間右端點f(i)排序，從左往右掃描區間，取出當前右端點坐標最小的區間，在該區間右端點坐標x射出一箭，答案加1，繼續往後掃描，去掉所有能被這支箭刺破的氣球（s(i)<=x的氣球均能被刺破），直到搜索到下一個不能被這隻箭刺破的氣球，再用同樣的方式處理。時間複雜度為排序的時間複雜度O(n*log(n))。

b. Follow up：

本題的輸出答案與所有區間中能選出的最多的互不重疊的區間的個數有什麼關係？

參考程序

九章演算法 - 幫助更多中國人找到好工作，矽谷頂尖IT企業工程師實時在線授課為你傳授面試技巧

面試官角度分析

這題與經典的活動選擇問題十分相似，解法是貪心演算法，能有清晰的思路並給出解答即可hire。

lintcode相關問題

合併區間

推薦閱讀：