문제
선물 포장 공장을 말아먹은 욱제는 계곡에서 백숙을 파느라 학교에 자주 가지 못한다. 하지만 월클의 인생은 피곤한 법! 욱제는 지금처럼 힘든 시기에도 자신을 기다리는 5조5억명의 열렬한 팬들을 위해 가끔씩 학교에 가 줘야 한다. 욱제는 백숙이 끓는 걸 지켜봐야 해서 가게를 오래 비울 수 없다. 그래서 욱제는 한 번 학교에 간 뒤 최소 시간동안 머물다가 모든 팬들과 한 번씩 인사를 하고 학교를 떠나려고 한다.
욱제는 임의의 시각에 학교에 오거나 학교를 떠날 수 있고, 단 한 번의 왕복만 한다. 동시에 여러 팬들에게 인사를 끝낼 수도 있다. 욱제는 잘생겨서 인사하면 팬들이 심쿵사로 바로 쓰러지기 때문에 인사를 하는데 소요되는 시간은 0이라고 하자.
예를 들어 3명의 팬 A, B, C가 학교에 머무르는 시간이 <그림 1>과 같다고 하자. 이 경우 시각 2에 3명의 팬이 모두 학교에 있으므로, 욱제는 시각 2에 학교에 와서 3명에게 동시에 인사를 하고 바로 가게로 돌아갈 수 있다. 시각 3이나 4도 마찬가지이다. 이때 욱제가 학교에 머무는 시간의 총합은 0이다.
다른 예로 2명의 팬 A와 B가 학교에 있는 시간이 <그림 2>와 같다고 하자. 욱제는 시각 4부터 시각 5까지 학교에 머물면서 시각 4에 A와, 시각 5에 B와 인사를 하고 학교를 떠날 수 있다. 이때 욱제가 학교에 머무는 시간은 1이다.
백숙집 주방 이모 효빈이는 N명의 팬들이 학교에 머무르는 시간 [s, e]들을 몰래 조사했다. 효빈이는 욱제가 학교에 머무르는 시간을 계산해서 그 시간동안 땡땡이를 치기로 했다. 효빈이와 함께 욱제가 학교에 머무르는 최소의 시간을 계산해 보자!
입력
첫째 줄에 욱제의 열렬한 팬의 수 N이 주어진다. (1 ≤ N ≤ 100,000)
둘째 줄부터 N개의 줄에 걸쳐, 각 줄에 정수 si, ei (1 ≤ si ≤ ei ≤ 100,000)가 순서대로 주어진다. 이는 i번째 팬이 학교에 있는 시간 [si, ei]을 의미한다.
출력
욱제가 학교에 머물러야 하는 최소의 시간을 출력한다.
풀이
생각보다 간단한 문제다. 끝나는 시간이 가장 빠른 시간에 시작하는 시간이 가장 늦은 시간을 뺀 값을 출력한다.
만약 그 값이 음수면 모든 학생이 겹칠 수 있는 시간대가 있으므로 0을 출력한다.
소스코드
import java.util.*;
import java.io.*;
public class Main{
public static void main(String [] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringBuilder sb = new StringBuilder();
StringTokenizer st;
final int NUMBER_OF_FAN = Integer.parseInt(br.readLine());
int mostStartPoint = -1,
lowestFinishPoint = 1000001;
for(int i=0;i<NUMBER_OF_FAN;i++) {
st = new StringTokenizer(br.readLine());
int start = Integer.parseInt(st.nextToken()),
finish = Integer.parseInt(st.nextToken());
if(start > mostStartPoint) {
mostStartPoint = start;
}
if(finish < lowestFinishPoint) {
lowestFinishPoint = finish;
}
}
int answer = mostStartPoint - lowestFinishPoint;
if(answer < 0) {
sb.append(0);
}else {
sb.append(answer);
}
sb.append("\n");
bw.write(sb.toString());
bw.flush();
br.close();
bw.close();
}
}