[백준 13334] 철로 / 자바 / 라인스위핑 **

#문제         

레벨: G2
알고리즘: 라인 스위핑 
풀이시간: 1시간
힌트 참조 유무: 유

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

---

#문제 풀이        

라인 스위핑 을 직역하면 싹스리 하는 이라는 뜻이다. 한 마디로 한 쪽 방향으로 정렬된 직선을 스캔하며 정해진 기준에 따라 답을 업데이트 하는 것이다. 그리드 알고리즘의 종류라고 생각하면 된다.

이 문제는 끝점을 기준으로 오름차순 정렬한다. 놓아야 하는 직선 L을 정렬된 끝점에 맞추어 계속해서 대보는 것이다. 기준에 부합하면 시작점을 큐에 넣고 L보다 튀어나온 큐에 있는 시작점들은 Poll 해준다. 간단하지 않은가?

 

+라인스위핑 문제느 변수를 사용해서 답을 관리하는 것보다 우선순위 큐의 사이즈로 관리하는 것이 용이하다.!!!!!!!!!!

---

#풀이 코드      

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

class Pair implements Comparable<Pair> {
    int start, end;

    Pair(int start, int end) {
        this.start = Math.min(start, end);
        this.end = Math.max(start, end);
    }

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        List<Pair> pairs = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            String[] input = br.readLine().split(" ");
            int h = Integer.parseInt(input[0]);
            int o = Integer.parseInt(input[1]);
            pairs.add(new Pair(h, o));
        }

        int d = Integer.parseInt(br.readLine());

        // 끝점을 기준으로 정렬
        Collections.sort(pairs);

        PriorityQueue<Integer> pq = new PriorityQueue<>();
        int maxCount = 0;

        for (Pair pair : pairs) {
            // 현재 pair의 끝점에서 d를 뺀 값보다 작은 시작점은 제거
            while (!pq.isEmpty() && pq.peek() < pair.end - d) {
                pq.poll();
            }

            // 현재 pair의 시작점이 범위 안에 들어오면 추가
            if (pair.start >= pair.end - d) {
                pq.offer(pair.start);
            }

            // 최대 개수 갱신
            maxCount = Math.max(maxCount, pq.size());
        }

        System.out.println(maxCount);
    }
}