import sys
input = sys.stdin.readline
N = int(input())
info = []
for i in range(N):
info.append(tuple(sorted(map(int,input().split()))))
D = int(input())
home = []
com = []
for i in range(N):
h,c = info[i]
if c-h > D:
continue
home.append(h)
com.append(c)
home.sort()
com.sort()
N = len(home)
cnt = result = 0
start = end = 0
while True:
if start == N:
break
if start != 0:
cnt -= 1
if h == home[start]:
start += 1
continue
h = home[start]
while end<N and com[end] <= h+D:
end += 1
cnt += 1
result = max(cnt,result)
start += 1
print(result)
투 포인터 알고리즘을 이용해서 해결하였다.
요약하면
1. 집 좌표와 회사 좌표 중 더 작은 좌표를 집 좌표라고 가정한다.
2. 집 좌표와 회사 좌표간의 거리가 D를 넘는 경우는 필요 없으므로 제외한다.
3. 집 좌표 따로, 회사 좌표 따로 sort한다.
4. 가장 작은 집 좌표에서 시작, (집좌표 + D) 거리까지 존재하는 회사 개수만큼 + 해준다.
5. 다음 집 좌표로 이동할때마다 집이 하나씩 범위 밖으로 나가므로 -1을 해준다.
처음에는 투포인트 + 투포인트 로 4포인트 알고리즘처럼 풀려고 했었다.
그러다가 집과 회사사이의 거리가 D를 넘는 경우를 제외하면 투포인트로 풀 수 있다는 것을 알게되었다.
다른 사람들은 heapq를 이용해서 푼 경우가 많았다. 사실 원리 자체는 거의 똑같다. sort를 쓰느냐 heapq를 쓰느냐의 차이라서
오늘의 교훈) 불필요한 조건을 제외하고 문제를 해결하자