문제
1차원 벽에 벽보들이 붙어 있다. 1차원 벽의 길이는 10,000,000 이다.
벽보들은 다른 벽보를 부분적으로 또는 완벽히 덮기도 한다. 조금이라도 보이는 벽보의 수는 몇 개인지 구하자.
입력
먼저 벽보의 수 1 ≤ n ≤ 10,000 이 입력된다. 다음 n줄에 거쳐 벽보의 정보가 주어진다.
벽보의 입력 순서는 붙이는 순서와 같다. 즉 위에 붙는 벽보가 나중에 입력된다.
각 벽보마다 두 정수 li and ri 가 주어진다.
이는 벽보가 벽의 li 번째 칸부터 ri 번째 칸까지 붙여져 있다는 뜻이다.
1 ≤ i ≤ n, 1 ≤ li ≤ ri ≤ 10,000,000.
출력
모든 벽보가 붙은 후에 조금이라도 보이는 벽보의 수를 모두 세어 출력한다.
예제
5
1 4
2 6
8 10
3 4
7 10
4
출처
Alberta Collegiate Programming Contest 2003.10.18, PKU 2528
로그인해야 코드를 작성할 수 있어요.