MaxNonoverlappingSegments

코딜리티

• A 배열에는 시작점이 들어가 있고, B 배열에는 끝점이 들어가 있다.
• 주어진 갯수만큼 선들이 있으며, 겹치지 않고 가질 수 있는 최대의 갯수를 구하기
• N의 범위는 0 <= N <= 30,000
• 각 숫자 범위는 0..1,000,000,000

접근 방식

: 정렬해서 처음 끝점을 기준으로 다음 시작점이 더 크다면 처음 끝점을 업데이트하고 카운트 업.

주의할 점

끝점을 기준으로 오름차순 정렬 먼저 한 뒤 시작점을 기준으로 오름차순해야한다.

코드

def solution(A, B):
    if len(A) == 0 or len(B) == 0:
        return 0

    arr = []
    for a, b in zip(A, B):
        arr.append((a, b))
    arr.sort(key=lambda x : (x[1], x[0]))
 
    s = arr[0][1]
    cnt = 1
    for i in range(1, len(arr)):
        if arr[i][0] > s:
            cnt += 1
            s = arr[i][1]
  
    return cnt