452. Minimum Number of Arrows to Burst Balloons
Notation
For convenience, we say the k^{th} ballon as b_{k}, first element of b_{k} as s_{k}, the second element of b_{k} as e_{k}, the total number of ballons as n.
Algorithm Description
(* If n = 0, directly return 0. The following is talking about the other case, when there are ballons. )

First sort the array according to their s_{k}

Then we define S_{k} and E_{k} as follows (Intuitively, if the intersection of the b_{k} and the [S_{k1} , E_{k1}] exsits then [S_{k}, E_{k}] is that intersection, else [S_{k}, E_{k}] is b_{k}):

S_{k} is always same as s_{k}

 If k = 0, E_{k}=e_{k}.
 Else if k > 0:
 If s_{k} ≤ E_{k1} and e_{k} > E_{k1} (It's c_{1}, short for case 1):
 E_{k} = E_{k1}
 If s_{k} > E_{k1} (also means e_{k} > E_{k1}) (It's c_{2}, short for case 2):
 E_{k} = e_{k}
 If e_{k} ≤ E_{k1} (also means S_{k1} < s_{k} < E_{k1}) (It's c_{3}, short for case 3):
 E_{k} = e_{k}
 If s_{k} ≤ E_{k1} and e_{k} > E_{k1} (It's c_{1}, short for case 1):
Since s_{k} is nondecreasing with k increasing, the above definition is complete (c_{1}, c_{2} and c_{3} cover all possible cases) and unique.


Now initially, set result r as 1, get S_{1} and E_{1} from b_{1}, do the following iteration:
 For every k (from 2 to n):
 if c_{1} or c_{3}:
 r remain same
 if c_{2}:
 r increase by 1
 anyway get S_{k} and E_{k} according to definition
 if c_{1} or c_{3}:
 Return r
 For every k (from 2 to n):
Proof
For convenience, we say the result is r_{t} after the t^{th} iterateration.
(1). This algorithm will terminate in at most O(nlogn) time if n is finite.
(1) is proved because if we use merge sort, it takes O(nlogn) time to finish the sorting part. This is followed by n iterations where each iteration takes constant time.
(2.1)For the first ballon, this algorithm result r _{1} is correct and the r_{1}^{th} arrow could be placed anywhere between [S_{1}, E_{1}]
(2.1) is obviously correct.
(2.2) If for the first t^{th} ballons, r_{t} is correct and the r_{t}^{th} arrow could be anywhere between [S_{t}, E_{t}], then for the first t+1^{th} ballons, r_{t+1} is correct and the r_{t+1}^{th} arrow could be anywhere between [S_{t+1}, E_{t+1}]. (t = 1, 2, 3...)
For different cases of b_{t+1}
 If c1 and c3:

Since there is intersection i_{t+1} between [s_{t+1}, e_{t+1}] and [S_{t}, E_{t}] and the r_{t}^{th} arrow could be anywhere between [S_{t}, E_{t}], let the arrow in i_{t+1}, which is both inside [S_{t}, E_{t}] and b_{t+1}, then r remains same, that is r_{t+1} = r_{t} so r is correct according to the algorithm.
In this case, [S_{t+1}, E_{t+1}] is exactly i_{t + 1}, so according to above paragraph, the r_{t+1}^{th} arrow could be anywhere between [S_{t+1}, E_{t+1}]

 If c2:
 Since s_{t+1} > E_{t} and E_{t} is at most e_{t}, so there is no intersection between any of the ballons with b_{t+1}. Thus r need to be increased by 1 to cover b_{t+1}, that is r_{t+1} = r_{t} + 1, according to the algorithm r_{t+1} is correct and the new arrow, a.k.a the r_{t+1}^{th} arrow could obviously be anywhere in [S_{t+1}, E_{t+1}], which is also b_{t+1}
Thus, (2.2) is proved.
According to (2.1) and (2.2), this algorithm returns correct result for any finite valid input.