[codility] Greedy MaxNonoverlappingSegments

https://app.codility.com/programmers/lessons/16-greedy_algorithms/max_nonoverlapping_segments/

MaxNonoverlappingSegments coding task - Learn to Code - Codility

def solution(A, B):
    if len(A) == 0:
        return 0 
 
    last_idx = 0
    cnt = 1
 
    for idx in range(1, len(A)):
        if B[last_idx] < A[idx]:
            cnt += 1
            last_idx = idx
 
    return(cnt)

문제 : A, B 배열에 선분의 시작과 끝 점이 주어진다. 배열 B는 오름차순으로 정렬 되어 있다. 

겹치지 않고 같이 있을 수 있는 선분의 최대 갯수를 반환. 

 

해결 과정:

담아 놓은 선분과 현재 비교하는 선분이 겹치지 않으면 갯수를 더한다. 

 

담아 놓은 선분과 현재 선분이 겹치지 않았다고 해서 어떻게 최대 선분 갯수를 포함하는 것을 보장할 수 있을까? 

 

*배열 B가 오름차순으로 정렬되어 있다는 점에 주목해야 한다. 

 

최대한 많은 선분을 담으려면 담겨진 선분의 끝점이 작으면 작을 수록 좋다. 

선분의 끝점 + 1 이 선분을 담을 수 있는 범위이기 때문이다. 

 

놓친 부분:

배열이 비어있는 경우 예외처리

B 정렬이 되어 있다는 점 빨리 캐치 못 함... 

 

쓸데 없이 너무 어렵게 생각했다.