백준 13334 철로(JAVA)

https://www.acmicpc.net/problem/13334

13334번: 철로

 

끝점을 기준으로 정렬하고 우선순위 큐를 활용한다.

 

끝점을 기준으로 오름차순 정렬을 하면 아래 그림처럼 된다. 

 

이 상태에서 집과 회사 중 더 작은 값을 기준으로 정렬한다.

 

여기서 유의해야하는게, 무조건 집이 회사보다 왼쪽에 있다고 생각하기 쉬운데 그렇지 않다. 

 

그림으로 보자면

 

이렇게 두 가지 경우가 가능하다. 그러므로 입력값을 받을 때 대소 비교를 통해서 일관성을 갖춰야 한다.

 

아무튼 

 

왼쪽에 있는 점을 기준으로 우선순위 큐를 돌리면서 그 top 값 vs 끝점 - length 를 비교한다.

 

말로하면 힘든데 코드로 보면 간단하다!

 

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

public class boj13334 {

    static class Pair implements Comparable<Pair> {
        int start, end;
        Pair(int a, int b){
            start = a; end = b;
        }


        @Override
        public int compareTo(Pair o) {
            return Integer.compare(this.end, o.end);
        }
    }

    static int N, length;
    static ArrayList<Pair> pairs = new ArrayList<>();

    public static void main(String[] args) {
        try{
            BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
            BufferedReader br =new BufferedReader(new InputStreamReader(System.in));
            StringTokenizer st = new StringTokenizer(br.readLine());

            N = Integer.parseInt(st.nextToken());
            for(int i = 0; i < N ; i++){
                st = new StringTokenizer(br.readLine());
                int a, b;
                a = Integer.parseInt(st.nextToken());
                b = Integer.parseInt(st.nextToken());
                if(a >b){
                    int temp = a;
                    a = b;
                    b = temp;
                }

                pairs.add(new Pair(a,b));
            }

            length = Integer.parseInt(new StringTokenizer(br.readLine()).nextToken());

            Collections.sort(pairs);

            PriorityQueue<Integer> pq = new PriorityQueue<>();

            int count = 0, maximum = 0;
            for (Pair pair : pairs) {
                while (!pq.isEmpty() && pq.peek() < pair.end - length) {
                    pq.poll();
                    count--;
                }

                if (pair.start >= pair.end - length) {
                    count++;
                    pq.add(pair.start);
                }

                maximum = Math.max(maximum, count);
            }
            bw.write(maximum + "\n");
            bw.flush();
        } catch(Exception e){
            e.printStackTrace();
        }
    }
}