BOJ 8539 LinkNet

문제 링크:

문제 내용

여러 대의 컴퓨터가 선형 링크 네트워크를 통해서 통신하려고 합니다. $a$번 노드에 접속한 컴퓨터와 $b$번 노드에 접속한 컴퓨터가 서로 통신할 때 $a$ 이상 $b$ 이하의 번호를 갖는 모든 노드를 점유하게 되며, 각 노드는 동시에 두 개의 통신을 할 수 없습니다. 서로 노드가 겹치지 않는 여러 개의 통신은 동시에 이루어질 수 있으며, 이러한 모든 통신을 처리하는 데에는 1초가 걸립니다.

이때, 주어진 통신 요청을 모두 처리하기 위해 필요한 최소 시간이 몇 초인지 구하세요.

입력

첫 줄에는 통신 요청의 개수 $N$이 주어집니다. ($0 \le N \le 100\;000$)

다음 줄부터 각 줄에 각각의 통신 요청에서 두 컴퓨터가 접속한 노드의 번호 $a$, $b$가 주어집니다. ($0 \le a < b \le 10^9$)

출력

문제의 정답을 출력합니다.

문제 풀이