[코드트리] 겹치지 않게 선분 고르기 Python

# n 입력
n = int(input())
# segment
segment = []
# 선분 입력
for _ in range(n):
    segment.append(tuple(map(int, input().split())))

# is_duplicated(curr_segment_idx)
def is_duplicated(curr_segment_idx):

    # linear
    linear = [
        0 for _ in range(1001)    
    ]

    # 표시해주기
    for idx in curr_segment_idx:
        # unpacking
        sx, ex = segment[idx]
        for i in range(sx, ex + 1):
            linear[i] += 1

    # linear을 돌면서
    for i in range(1001):
        # 겹치는게 발견되면
        if linear[i] >= 2:
            # 겹침
            return True
    
    # 다 돌면 안겹침
    return False

# is_possible(curr_idx, k)
def is_possible(curr_idx, k):
    # 전역변수 선언
    global max_segment
    # 종료조건
    if curr_idx == k+1:
        # 안겹치면
        if not is_duplicated(curr_segment):
            # max_segment update
            max_segment = k
        return 

    # 숫자 넣어주기
    for i in range(n):
        # 앞에것보다 작거나 같은 경우라면
        if len(curr_segment) and curr_segment[-1] >= i:
            # skip
            continue
        # 앞에것보다 큰 경우
        else:
            curr_segment.append(i)
            is_possible(curr_idx + 1, k)
            curr_segment.pop()

# 설계
# max_segment
max_segment = 1

for i in range(2, n+1):
    # curr_segment
    curr_segment = []
    # 가능한지 확인
    is_possible(1, i)

# 출력
print(max_segment)