python 백준 23740 버스 노선 개편하기

https://www.acmicpc.net/problem/23740

로직

• 버스 노선 개편 방식은 노선이 조금이라도 겹치면 한개의 노선으로 만들어 버리는 형식
• 시작점을 기준으로 정렬
• 0번 인덱스의 값을 S,E,C로 기록(새로 만들어지는 노선의 시작점, 끝점, 가격을 기록하는 변수)
• 1번 인덱스 값과 비교
  • 1번 인덱스의 시작점 s가 E보다 작거나 같으면 노선이 겹치는 것을 의미(시작점을 기준으로 정렬했으므로 s는 S보다 크거나 같을 수 밖에 없음)
  • 이 때 새로 만들어지는 노선의 끝점(E)는 0번 인덱스의 끝점과 1번 인덱스의 끝점 중 큰 값이 됨
  • 마찬가지로 가격(C)는 0번 인덱스의 가격과 1번 인덱스의 가격 중 싼 값으로 됨
• 만약 1번 인덱스의 시작점 s가 0번 인덱스의 끝점보다 크다면 둘은 다른 노선이 되고, 새로운 S,E,C가 됨
• 이 과정을 N개의 노선에 모두 적용

import sys
input = sys.stdin.readline # N의 값이 커서 대체

N = int(input())
graph = [list(map(int,input().split())) for _ in range(N)]
graph.sort()
S,E,C = graph[0]
ans = []
for s,e,c in graph:
    if s <= E:
        C = min(C,c)
        E = max(E,e)
    else:
        ans.append((S,E,C))
        S,E,C = s,e,c
if not ans or (ans[-1] != (S,E,C)):
    ans.append((S,E,C))
print(len(ans))
for value in ans:
    print(*value)