그리디
/
PGS 요격 시스템
Search
PGS 요격 시스템
생성일
2024/11/28 02:23
URL
https://school.programmers.co.kr/learn/courses/30/lessons/181188
태그
그리디 알고리즘
정렬
문제 설명
•
2차원 공간에서 주어진 폭격 미사일들의 x좌표 범위를 최소 개수의 요격 미사일로 모두 관통하여 요격해야 할 때, 필요한 최소 요격 미사일 수를 구하는 문제
예제 입력/출력
targets
result
[[4,5],[4,8],[10,14],[11,13],[5,12],[3,7],[1,4]]
3
제약 조건
•
1
≤
n
≤
500
,
000
1 ≤ n ≤ 500,000
1
≤
n
≤
500
,
000
◦
0
≤
s
<
e
≤
100
,
000
,
000
0 ≤ s < e ≤ 100,000,000
0
≤
s
<
e
≤
100
,
000
,
000
문제 풀이
접근1
브루트포스 -
O
(
n
⋅
2
n
)
O(n \cdot 2^n)
O
(
n
⋅
2
n
)
접근2
그리디 -
O
(
n
l
o
g
n
)
O(nlogn)
O
(
n
l
o
g
n
)
풀이 코드
접근2
그리디 -
O
(
n
l
o
g
n
)
O(nlogn)
O
(
n
l
o
g
n
)
