요격 시스템 (그리디)

 

https://school.programmers.co.kr/learn/courses/30/lessons/181188

프로그래머스

 

분석

 

• 끝값이 현재 시작값 보다 큰 경우
  1. 겹칩
  2. 끝값 유지
• 끝값이 현재 시작값보다 같거나 작은 경우
  1. 겹치지 않음
  2. 미사일 수 1 증가
  3.  시작값, 끝값 갱신

 

[[1, 4], [3, 7], [4, 5], [4, 8], [5, 12], [10, 14], [11, 13]]

nowStart	nowEnd	end	answer
		4	1
3	7	4	1
4	5	5	2
4	8	5	2
5	12	12	3
10	14	12	3
11	13	12	3

[2170] 선 긋기 (선의 총 길이 구하기)

 

풀이

def solution(targets):
    answer = 1
    
    targets.sort()
    
    end=targets[0][1]

    for i in range(1,len(targets)):
        nowStart,nowEnd=targets[i]        
        if end>nowStart:
            end = min(end, nowEnd)
        else: 
            answer+=1
            end=nowEnd

    return answer