[Leetcode] 452. Minimum Number of Arrows to Burst Balloons

문제 : https://leetcode.com/problems/minimum-number-of-arrows-to-burst-balloons/

---

points 배열을 start 기준 오름차순, start가 동일한 경우 end 기준으로 오름차순 정렬한다.

points 배열을 앞에서부터 탐색하면서 중복되는 범위를 저장해둔다. (let, duplicate)

duplicate 범위의 start가 end 보다 작아지는 경우 정답을 +1 하고 현재 탐색중인 points 배열 원소값으로 duplicate를 갱신한다.

 

문제의 예제 1번 예시. points = [[10,16],[2,8],[1,6],[7,12]]

[1, 6]	x -> [1, 6]	갱신 (정답 + 1)
[2, 8]	[2, 6]
[7, 12]	[7, 6] -> [7, 12]	갱신 (정답 + 1)
[10, 16]	[10, 12]

 

시간복잡도는 O(NlogN).

---

소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/medium/452.%20Minimum%20Number%20of%20Arrows%20to%20Burst%20Balloons.cpp