백준 13334번 철로 (JAVA)

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

13334번: 철로

 

저는 우선순위 큐를 이용해 문제를 해결하였습니다.

저는 회사와 집의 입력을 먼 곳을 기준으로 같다면 가까운 곳을 기준으로 오름차순 정렬하였습니다. 

이후 입력을 돌면서 가까운 곳이 먼곳 - 길이보다 큰 것은 우선순위 큐에 넣었습니다. 

그리고 우선순위 큐의 앞 값이 현재 먼 곳 - 길이보다 작다면 계속 우선순위 큐에서 빼주고 각각의 입력에 대해 우선순위 큐의 사이즈의 최대값을 찾고 이를 출력하였습니다.

 

package BOJ.greedy;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
import java.util.function.Function;

public class BOJ_13334 {

    static class Edge {

        int start;
        int end;

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

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        Function<String, Integer> stoi = Integer::parseInt;
        int n = stoi.apply(br.readLine());
        List<Edge> edges = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            int a = stoi.apply(st.nextToken());
            int b = stoi.apply(st.nextToken());
            edges.add(new Edge(Math.min(a, b), Math.max(a, b)));
        }
        int length = stoi.apply(br.readLine());
        edges.sort((o1, o2) -> {
            if(o1.end == o2.end){
                return o1.start - o2.start;
            }
            return o1.end - o2.end;
        });
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        int result = 0;
        for(Edge edge : edges){
            while(!pq.isEmpty() && pq.peek() < edge.end - length){
                pq.poll();
            }
            if(edge.start >= edge.end - length){
                pq.offer(edge.start);
            }
            result = Math.max(pq.size(), result);
        }
        System.out.println(result);
    }
}