[JAVA] 백준 강의실 1374

 

 

최근에 코테를 2개정도 봤는데 
이런 우선순위 큐를 사용한 그리디 문제를 2개 마주했었다. 

시작하는 시간과 끝나는 시간이 주어지고 내부적으로 다양한 조건이 존재하는 문제들이다.
이 문제는 간단하게 시작하는시간 끝나는 시간 그리고 겹칠경우 공간을 +1 해주면 되는 비교적 할만한 문제였다. 

 

// Online Java Compiler
// Use this editor to write, compile and run your Java code online
import java.util.*;
import java.io.*;


class Main {
    
    static class Lecture{
        int start;
        int fin;
        Lecture(int s, int f){
            this.start =s;
            this.fin =f;
        }
        
    }
    
    
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        int n = Integer.parseInt(br.readLine());
        
        PriorityQueue<Lecture> q = new PriorityQueue<>((o1, o2) -> o1.start-o2.start);
        
        for(int i =0; i<n; i++){
            String[] s = br.readLine().split(" ");
            int number = Integer.parseInt(s[0]);
            int start = Integer.parseInt(s[1]);
            int fin = Integer.parseInt(s[2]);
            q.offer(new Lecture(start, fin));
        }
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        Lecture l = q.poll();
        int answer = 1;
        pq.offer(l.fin);
        while(!q.isEmpty()){
            l = q.poll();
            int last = pq.peek();
            if(last > l.start){
                answer++;
            }else{
                pq.poll();
            }
            pq.offer(l.fin);
        }
        bw.write(String.valueOf(answer));
        bw.flush();
        bw.close();
    }

}