문제 바로가기

나의 풀이

쉬운 문제였다. 선 자체는 최대 백만개가 주어지므로 반복이 되어도 상관없지만, 값은 -10억 ~ 10억까지이므로 전체 범위를 순회하는 것은 시간 초과가 날 것이다.

따라서 Line 이라는 클래스를 만들고, 시작 시간을 기준으로 다른 객체와 비교하여 오름차순으로 정렬되도록 정의했다.

이후 나는 우선순위 큐를 활용했지만, 리스트를 사용한 다음 Collections.sort() 메소드를 사용해 정렬해도 상관 없을 듯 하다.

나의 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;

class Main {

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		Queue<Line> lines = new PriorityQueue<>();
		for (int i = 0; i < n; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			lines.offer(new Line(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())));
		}

		Line current = lines.poll();
		int answer = 0;
		if (current != null) {
			answer = current.getEnd() - current.getStart();
		}

		while (!lines.isEmpty()) {
			Line next = lines.poll();

			if (next.getEnd() <= current.getEnd()) {
				continue;
			}

			if (next.getStart() < current.getEnd()) {
				answer += next.getEnd() - current.getEnd();
				current = next;
				continue;
			}

			answer += next.getEnd() - next.getStart();
			current = next;
		}

		System.out.println(answer);
	}

	private static class Line implements Comparable<Line> {
		int start;
		int end;

		public Line(int start, int end) {
			this.start = start;
			this.end = end;
		}

		public int getStart() {
			return start;
		}

		public int getEnd() {
			return end;
		}

		@Override
		public int compareTo(Line target) {
			return Integer.compare(this.getStart(), target.getStart());
		}
	}
}