[JAVA] 백준 13334 철로

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

13334번: 철로

이런 문제는 항상 오름차순 정렬을 하고 봐야하는 것 같다.

정렬한 후에 주어진 선분을 정보의 왼쪽이나 오른쪽 끝 값에 대보며 개수를 구하고, 반대쪽에서 정답 만족하는지 체크

이 문제 같은 경우는 오른쪽에 선분을 맞춰 이동시키며 왼쪽에서 정답 만족하지 않는 출근길들 빼내기

 

아래 블로그가 굉장히 설명이 잘 되어있다.

https://chanhuiseok.github.io/posts/baek-28/

[백준] 13334번 - 철로

 

 

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

public class Main {
    public static class Info implements Comparable<Info>{
        int left, right;
        public Info(int l, int r){
            left = l; right = r;
        }
        public int compareTo(Info o){
            if(right==o.right) return left-o.left;
            else return right-o.right;
        }
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        ArrayList<Info> list = new ArrayList<>();

        for(int i=0;i<N;i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            list.add(new Info(Math.min(a,b), Math.max(a,b)));
        }

        int d = Integer.parseInt(br.readLine());
        Collections.sort(list);
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        int answer = 0;
        for(int i=0;i<N;i++){
            Info info = list.get(i);
            if(info.right - info.left>d) continue;

            pq.add(info.left);
            while(!pq.isEmpty()){
                if(info.right-pq.peek()<=d) break;
                pq.poll();
            }
            answer = Math.max(answer, pq.size());
        }

        System.out.println(answer);
    }
}