시간 복잡도 줄이는 기술 5. +1-1 technique

+1-1 Technique

N개의 선분을 2개의 시작, 끝 정점으로 나눠 각각 +1, -1 가중치를 줘서 x가 증가하는 순서대로 정렬하는 방법을 +1 -1 Technique

예시 - 수직선 상 겹치는 구간 

 

문제 - 가장 많이 겹치는 구간

일직선 위에 n개의 구간이 주어졌을 때, 구간이 가장 많이 겹치는 부분에서 몇 개의 구간이 겹치는지를 구하는 프로그램을 작성하세요.

아이디어

• 먼저, 배열을 생성해서 선분이 있는 구간마다 1을 더해 최댓값을 구하는 식은 시간초과가 났다.
• → 선분의 구간을 for로 돌며 1을 더하는 것이 문제
• 선분의 시작점과 끝점에 +1,-1을 한다. 모든 점마다 겹치는 선분을 세줌

코드

n=int(input())

arr= [tuple(map(int,input().split())) for _ in range(n)]
arr.sort()
points=[0]*200001

for x1,x2 in arr:
    points[x1]+=1
    points[x2]-=1

ans=0
overlapped_cnt = 0
for x in range(1, 200001):
    overlapped_cnt += points[x]
    ans = max(ans, overlapped_cnt)

print(ans)