[백준] 1931 회의실배정

문제보기

그리디 어렵다.. ㅠ_ㅜ 처음에 가긴증 처럼 풀려다가 계속 시간초과 떠서 검색검색 해가며 풀었다… 흑

내일은 그리디 많이 풀어야지 !

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

class Node{
  int start;
  int end;
  Node(int start, int end){
    this.start = start;
    this.end = 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<Node> list = new ArrayList<>();

    for(int i = 0 ; i < n ; i++ ){
      StringTokenizer st = new StringTokenizer(br.readLine());
      int start = Integer.parseInt(st.nextToken());
      int end = Integer.parseInt(st.nextToken());
      list.add(new Node(start, end));
    }
		
   	// 정렬기준은 끝나는 시간이 빠른 순으로!
    // 끝나는 시간이 같다면 시작 시간이 빠른 순으로!
    list.sort(new Comparator<Node>(){
      @Override
      public int compare(Node o1, Node o2){
        if(o1.end < o2.end){
          return -1;
        }else if(o1.end == o2.end){
          return o1.start - o2.start;
        }else{
          return 1;
        }
      }
    });

    int cnt = 1;
    int start = list.get(0).end; // 이러면 무적권 첫행부터 시작하는 부분수열이 최장수열이 됨
    for(int j = 1 ; j < n ; j++){
      if(list.get(j).start >= start){
        cnt++;
        start = list.get(j).end;
      }
    }

    System.out.println(cnt);

  }
}