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

[seungriyou]

452. Minimum Number of Arrows to Burst Balloons similar to #116

Approach

intervals의 intersection을 모두 구하고, 그 개수를 반환하면 된다.

Idea 1: Sort by s

interval의 s를 기준으로 오름차순 정렬하면, 다음과 같이 intersection의 개수를 구할 수 있다.

# 가장 최근(확인 중인) overlapped interval의 e
end = float("inf")
res = 1

for s, e in points:
    # intersect X
    if end < s:
        res += 1
        end = e
    # intersect O
    else:
        end = min(end, e)

return res

Idea 2: Sort by e 📌

interval의 e를 기준으로 오름차순 정렬하면, 다음과 같이 intersection의 개수를 구할 수 있다.

Note

이때, s를 기준으로 정렬했을 때는 intersect O 인 경우에 end 값을 min(end, e)로 업데이트 해주어야 했으나, e를 기준으로 정렬한다면 해당 로직이 필요하지 않다. 따라서 코드가 더 간결해진다.

points.sort(key=lambda x: x[1])

end = res = 0

for s, e in points:
    # intersect X
    if res == 0 or end < s:
        res += 1
        end = e

return res

Complexity

• Time: O(nlogn) (sorting)
• Space: O(1)