Super strict and detailed proved Greedy algorithm!!!


  • 0
    Z

    452. Minimum Number of Arrows to Burst Balloons

    Notation

    For convenience, we say the kth ballon as bk, first element of bk as sk, the second element of bk as ek, 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. )

    1. First sort the array according to their sk

    2. Then we define Sk and Ek as follows (Intuitively, if the intersection of the bk and the [Sk-1 , Ek-1] exsits then [Sk, Ek] is that intersection, else [Sk, Ek] is bk):

      1. Sk is always same as sk

        • If k = 0, Ek=ek.
        • Else if k > 0:
          • If sk ≤ Ek-1 and ek > Ek-1 (It's c1, short for case 1):
            • Ek = Ek-1
          • If sk > Ek-1 (also means ek > Ek-1) (It's c2, short for case 2):
            • Ek = ek
          • If ek ≤ Ek-1 (also means Sk-1 < sk < Ek-1) (It's c3, short for case 3):
            • Ek = ek

      Since sk is non-decreasing with k increasing, the above definition is complete (c1, c2 and c3 cover all possible cases) and unique.

    3. Now initially, set result r as 1, get S1 and E1 from b1, do the following iteration:

      • For every k (from 2 to n):
        • if c1 or c3:
          • r remain same
        • if c2:
          • r increase by 1
        • anyway get Sk and Ek according to definition
      • Return r

    Proof

    For convenience, we say the result is rt after the tth 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 r1th arrow could be placed anywhere between [S1, E1]

    (2.1) is obviously correct.

    (2.2) If for the first tth ballons, rt is correct and the rtth arrow could be anywhere between [St, Et], then for the first t+1th ballons, rt+1 is correct and the rt+1th arrow could be anywhere between [St+1, Et+1]. (t = 1, 2, 3...)

    For different cases of bt+1

    • If c1 and c3:
      • Since there is intersection it+1 between [st+1, et+1] and [St, Et] and the rtth arrow could be anywhere between [St, Et], let the arrow in it+1, which is both inside [St, Et] and bt+1, then r remains same, that is rt+1 = rt so r is correct according to the algorithm.

        In this case, [St+1, Et+1] is exactly it + 1, so according to above paragraph, the rt+1th arrow could be anywhere between [St+1, Et+1]

    • If c2:
      • Since st+1 > Et and Et is at most et, so there is no intersection between any of the ballons with bt+1. Thus r need to be increased by 1 to cover bt+1, that is rt+1 = rt + 1, according to the algorithm rt+1 is correct and the new arrow, a.k.a the rt+1th arrow could obviously be anywhere in [St+1, Et+1], which is also bt+1

    Thus, (2.2) is proved.

    According to (2.1) and (2.2), this algorithm returns correct result for any finite valid input.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.