BOJ 2170 : 선 긋기

문제링크

풀이요약

그리디

풀이상세

1. 입력의 시작 끝 값이 작은 순으로 나올 수 있도록 하는 우선순위 큐를 생성한다.

2. 다음 시작 값이 이전의 끝 값보다 큰 경우가 바로 선이 나뉘는 경우이며, 지금까지의 시작과 끝의 거리를 저장한다.

3. 2 에 해당하지 않는 경우가 선이 서로 겹치는 경우이다. 우선순위 큐를 통해 모든 시작과 끝 값은 이전 값보다 큰 거나 같은 값만 나타나는 것이 증명되므로, 큰 값만은 업데이트 한다.

import java.io.*;
import java.util.*;

public class Main {
    static PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> {
        if (a[0] == b[0]) return a[1] - b[1];
        return a[0] - b[0];
    });
    static int N, ans;

    private static void input() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        for (int i = 0; i < N; i++) {
            StringTokenizer stk = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(stk.nextToken());
            int b = Integer.parseInt(stk.nextToken());
            pq.add(new int[]{a, b});
        }
    }

    private static void solve() {
        int l = pq.peek()[0];
        int r = pq.peek()[1];
        pq.poll();
        while (!pq.isEmpty()) {
            int[] n = pq.poll();
            if (n[0] >  r) {
                ans += (r - l);
                l = n[0];
                r = n[1];
            } else if(n[1]>r) r = n[1];

        }
        ans += (r - l);
    }

    private static void output() {
        System.out.println(ans);
    }

    public static void main(String[] args) throws Exception {
        input();
        solve();
        output();
    }
}