회의실 배정(1931)

회의실 배정(1931)

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

public class Main {

  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    StringBuilder sb = new StringBuilder();
    
    int n = Integer.parseInt(br.readLine());
    
    Time time;
    
    Queue<Time> pq = new PriorityQueue<>();
    
    for(int i = 0; i < n; i++){
      StringTokenizer st = new StringTokenizer(br.readLine());
      
      int s = Integer.parseInt(st.nextToken()), e = Integer.parseInt(st.nextToken());
      
      time = new Time(s, e);
      
      pq.add(time); 
    }
    
    int cnt = 0;
    int endTime = 0;
    
    for(int i = 0; i < n; i++) {
      Time target = pq.poll();
      if(endTime <= target.getS()) {
        endTime = target.getE();
        cnt++;
      }
    }
    
    sb.append(cnt);
    
    bw.write(sb.toString());
    bw.flush();
    bw.close();
    br.close();
  }

  public static class Time implements Comparable<Time>{
    private int s;
    private int e;
    
    public Time(int s, int e) {
      super();
      this.s = s;
      this.e = e;
    }

    public int getS() {
      return s;
    }

    public int getE() {
      return e;
    }

    @Override
    public int compareTo(Time o) {
      if(this.e < o.getE()) return -1;
      else if(this.e > o.getE()) return 1;
      else {
        if(this.s < o.getS()) return -1;
        else return 1;
      }
    }    
  }
}

풀이과정

1. 처음 회의 시간을 기준으로 가능한 시간들을 하나하나 처리하며 카운트를 하려고 했었다.
2. 그래서 DFS를 사용해보려고 했는데, 입력받은 시간들을 하나의 객체로 만들고, 조건을 제공하여 각 노드들을 간선으로 연결을 하려고 하니 어려움이 있었다.
3. 그래서 알아보니 그리디 알고리즘의 문제였다.

- 성공
- 메모리 : 41868 KB
- 시간 : 488 ms

보안점

1. 그리디 알고리즘에 대한 공부를 해봐야겠다