15922 아우으 우아으이야!! (Java)

아우으 우아으이야!!

문제

아우으 우아으이야!! 으어아아아아아아아ㅏㅏㅏ아아앙ㅇ아아ㅏ

수직선 위에 선분을 여러 개 그릴 거 야아아앙ㅇ아아아ㅏㅏ아아ㅏㅏ!!

선분을 겹치게 그리는 것도 가능하다아어으우어우으아아아아아아아아아이야!!!!1

선분을 모두 그렸을 때, 수직선 위에 그려진 선분 길이의 총합은 얼마아아으으우어으이으야이야!!!!

입력

첫째 줄에 수직선 위에 그릴 선분의 개수 N이 주어진다아우으 우아으이야!!. (1 ≤ N ≤ 100,000)

둘째 줄 부터 N개의 줄에 좌표를 나타내는 정수쌍 (x, y)가 주어진다으어아아아아아아아ㅏㅏㅏ아아앙ㅇ아아.

이는 [x, y] 구간 (x와 y를 포함하는 구간)에 선분을 그린다는 의미이다유아아우응아이양.

좌표는 x가 증가하는 순으로, x가 같다면 y가 증가하는 순으로 주어진다으우오아앙아ㅓㅇ아ㅡㅇ. (-1,000,000,000 ≤ x < y ≤ 1,000,000,000)

출력

N개의 선분을 모두 그렸을 때, 수직선 위에 그어진 선분 길이의 총합을 출력한다아아어으잉에애야우아으아이아야아아아아아아이야!!!

풀이

수직선 위에 선분을 그려 그 길이의 합을 구하는 단순한 문제같지만 범위가 매우 크기 때문에 단순하게 접근하면 시간초과가 발생할 것이다.
우리가 선분을 그을때를 생각해 보자.
좌표는 x가 증가하는 순으로, x가 같다면 y가 증가하는 순으로 주어지므로 다음으로 오는 선분은 앞에 있던 선분보다는 항상 오른쪽에 있다는 것을 알 수 있다.
그러면 우리가 고려해야 하는 것은 총 3가지 이다.

1. 겹치는 부분이 없는 경우
2. 다음으로 오는 선분의 일부분이 겹치는 경우
3. 다음으로 오는 선분이 앞에 있는 선분 안에 들어가 있는 경우

위의 3가지 경우 모두 앞에서 그렸던 선분의 시작점과 끝점만 알면 해결 가능하다는 것을 알 수 있다.
1번의 경우 다음으로 오는 선분의 시작점이 앞서 그렸던 선분의 끝점보다 큰 경우이다.
2번의 경우 다음으로 오는 선분의 시작점이 앞서 그렸던 선분의 끝점보다 작거나 같으면서
다음으로 오는 선분의 끝점이 앞서 그렸던 선분의 끝점보다 큰 경우이다.
3번의 경우 다음으로 오는 선분의 시작점이 앞서 그렸던 선분의 끝점보다 작거나 같으면서
다음으로 오는 선분의 끝점이 앞서 그렸던 선분의 끝점보다 작거나 같은 경우이다.

이를 잘 생각해서 구현하면 된다.
나는 우선순위 큐를 내림차순으로 구현하여 선분들의 시작점과 끝점을 집어넣어 활용하면서 문제를 해결하였다.

풀이

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

public class Main{

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        int ans = 0;
        PriorityQueue<Integer> queue = new PriorityQueue<>(Collections.reverseOrder());

//        queue.add(-5);
//        queue.add(-2);
//        queue.add(-3);
//        queue.add(0);
//        System.out.println();
//        while (!queue.isEmpty()) {
//            System.out.print(queue.poll() + " ");
//        }
//        System.out.println();
        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());

            if (queue.isEmpty()) {
                queue.add(start);
                queue.add(end);
                continue;
            }

            int endPoint = queue.peek();
            if (endPoint >= start) {
                queue.poll();
                end = Math.max(endPoint,end);
                queue.add(end);
            }else{
                int second = queue.poll();
                int first = queue.poll();
                ans += second - first;
                queue.add(start);
                queue.add(end);
            }

        }
        int second = queue.poll();
        int first = queue.poll();
        ans += second - first;

        System.out.println(ans);

    }
}