[JAVA]백준 그리디 알고리즘 자바로 풀기(회의실배정 1931번)

문제

한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의들에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 최대수의 회의를 찾아라. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다.

 

입력

첫째 줄에 회의의 수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N+1 줄까지 각 회의의 정보가 주어지는데 이것은 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다. 시작 시간과 끝나는 시간은 231-1보다 작거나 같은 자연수 또는 0이다.

 

출력

첫째 줄에 최대 사용할 수 있는 회의 수를 출력하여라.

 

예제 입력 1

11 1 4 3 5 0 6 5 7 3 8 5 9 6 10 8 11 8 12 2 13 12 14

예제 출력 1 

4

package com.algo.controller;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.StringTokenizer;

public class Code{
    public static void main(String[] args) throws IOException  {
    	
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
     
    //회의의 수를 입력받는다.
    int num = Integer.parseInt(br.readLine());
 
    int[][] time = new int[num][2];
    
    //회의 시작시간과 끝나는시간을 2차원배열에 입력받는다.
    for(int i=0; i<num; i++) {
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	for(int j=0; j<2; j++) {
    		time[i][j] = Integer.parseInt(st.nextToken());
    	}
    }
    
    //끝나는 시간을 기준으로 정렬을 하고, 같을 경우에는 시작시간을 기준으로 다시 정렬한다.
    Arrays.sort(time, new Comparator<int[]>() {
       
    	@Override
        public int compare(int[] start, int[] end) {
                   
    		if(start[1]==end[1]){
                //종료시간이 같을 경우, 시작시간으로 정렬한다.
                return Integer.compare(start[0], end[0]);
            }
            //종료시간으로  정렬한다.
            return Integer.compare(start[1], end[1]);
        }

    });
    
    int count = 0;    // 최대값 변수 
    int end = -1;    // 다음시작 시간과 비교할 변수
    
    for (int i = 0; i < num; i++) {
        
    	//현재 시작시간이 이전 종료시간보다 늦을 경우(1 4 와 3 5 처럼) 
        if (time[i][0] >= end) {
  
            end = time[i][1]; //현재 종료시간을 다음 시작시간과 비교하기위해 저장 
            count++;
        }
    }
    System.out.println(count);
    br.close();
}
}