문제
정올이는 사무직을 맡고 있는데, N 개의 회의들을 정렬하라는 지시를 받았다.
모든 회의는 시작 시간과 끝 시간, 두 개의 자연수로 표현된다.
예를 들어 3 10 회의는, 3시에 시작하여 10시에 끝나는 회의이다. ( 길이는 7시간일 것이다. )
정올이는 이 회의들을 정렬할 것인데,
1 순위 : 회의의 길이
2 순위 : 회의 시작 시간으로 오름차순 정렬하고 싶다.
즉, 길이가 가장 짧은 회의가 앞으로 오게 하고,
길이가 같은 회의들끼리는 먼저 시작하는 것을 앞으로 오게 할 것이다.
정올이를 도와 정렬 결과를 출력하자.
입력
첫 줄에 N 이 입력된다. ( 1 ≤ N ≤ 500,000 )
이후 N 줄에 걸쳐, 각 회의의 시작 시간 S 와 끝 시간 E 가 입력된다.
( 1 ≤ S ≤ E ≤ 109 )
단, 입력되는 회의들 중에서 S 와 E 가 모두 같은 회의가 여러 번 등장하는 경우는 없다.
입출력의 양이 많으므로, 빠른 입출력을 사용하는 것을 권장합니다. 다음은 대표적인 언어에서 빠른 입출력을 이용하는 방법입니다.
C++:
cin,cout을 사용한다면main함수 첫 줄에std::cin.tie(0); std::ios::sync_with_stdio(false);를 추가하고, 줄바꿈 시endl대신'\n'을 출력해주세요. 이 경우scanf를 비롯한 C의 입출력 함수는 사용할 수 없음에 유의해 주세요.
scanf/printf는 충분히 빠르므로 별도의 처리를 하지 않아도 괜찮습니다.Java:
Scanner와System.out.println대신BufferedReader와BufferedWriter를 사용해 주세요.Python3, PyPy3:
input()대신sys.stdin.readline().rstrip()을 사용해 주세요.
출력
정렬한 결과에서, 각 회의들의 "입력 순서"를 차례대로 출력하자.
"입력 순서"란, 몇 번째로 입력 되었는지를 나타낸다.
예를 들어, 처음에 입력된 회의의 "입력 순서"는 1 , 그 다음은 2 , ... 마지막은 N 일 것이다.
예제
7
3 5
1 3
7 10
2 8
1 7
8 8
2 4
6
2
7
1
3
5
4
로그인해야 코드를 작성할 수 있어요.