[코드트리] 가장 많이 겹치는 구간 (+1-1 technique)

문제

https://www.codetree.ai/missions/8/problems/section-with-maximum-overlap?&utm_source=clipboard&utm_medium=text

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

---

소스코드

n = int(input())
line = []

for i in range(n):
    a, b = map(int, input().split())
    line.append((a, 1))
    line.append((b, -1))
line.sort()

maxvar = 0
var = 0 
index = 0 
maxindex = 0 
for i in range(len(line)):
    var += (line[i])[1]
    if var > maxvar:
        maxvar = var
        maxindex = i
print(maxvar)

 

 

 

위 같이 선분이 주어지면 선분 튜플을 저장하는 리스트를 생성합니다. 선분 시작점은 1, 끝점은 -1로 정하고 리스트를 정렬한 뒤 임의의 변수에 더하면서 좌표의 처음부터 끝까지 max 값을 체크하면 되는 문제입니다.