링크

2170 선 긋기

문제

풀이

이 문제는 그리디 문제이다.
시작을 기준으로 오름차순 정렬을 하고 시작이 같으면 끝나는 지점을 기준으로 내림차순을 했다.
파악해야 되는 유형이 3가지가 있는데
1. (1, 10), (2, 5)와 같이 포함되는 유형
2. (1, 4), (2, 6)와 같이 이어지는 유형
3. (1, 3), (5, 7)와 같이 분리된 유형

1번 경우는 1, 10으로만 계산하고 패스
2번 경우는 1, 4계산하고 4, 6 계산하고 패스
3번은 1, 3계산하고 5, 7 따로따로 계산하고 패스
로 진행했다.

밑에 코드에서
if(prevEnd >= currentStart) 이 부분은 1번과 2번 유형에 해당한다.
그리고 1번유형은 1, 10만 계산하고 2, 5는 계산해서 더해주면 안되기 때문에
if(prevEnd > currentEnd) continue를 통해 패스한다.
else문은 3번 유형이다.

코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.*;

class Node implements Comparable<Node>{
    int start;
    int end;

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

    @Override
    public int compareTo(Node o){
        if(o.start == this.start){
            return o.end - this.end;
        }

        return this.start - o.start;
    }

}

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));

        int n = Integer.parseInt(br.readLine());
        PriorityQueue<Node> pq = new PriorityQueue();
        for(int i=0;i<n;i++){
            String[] arr = br.readLine().split(" ");

            pq.add(new Node(Integer.parseInt(arr[0]), Integer.parseInt(arr[1])));
        }

        int answer = 0;

        Node first  = pq.poll();
        answer += Math.abs(first.end - first.start);
        int prevEnd = first.end;

        while(!pq.isEmpty()){
            Node node = pq.poll();
            int currentStart = node.start;
            int currentEnd = node.end;
//            System.out.println("currentStart = " + currentStart + ", currendEnd = " + currentEnd);
//            System.out.println("prevEnd = " + prevEnd);
//            System.out.println("answer = " + answer);

            if(prevEnd >= currentStart){
                if(prevEnd > currentEnd) continue;
                answer += Math.abs(prevEnd - currentEnd);
            } else{
                answer += Math.abs(currentEnd - currentStart);
            }

            prevEnd = currentEnd;
        }


        System.out.println(answer);




    }


}