[JAVA] 강의실 배정

https://softeer.ai/practice/6291

Softeer - 현대자동차그룹 SW인재확보플랫폼

 

언어별 시간/메모리

언어시간메모리

JavaScript	5초	256MB
C	1초	256MB
C++	1초	256MB
Java	5초	256MB
Python	5초	256MB
C#	2초	256MB
Kotlin	2초	256MB
Go	2초	256MB
Swift	2초	256MB

김교수는 강의실 1개에 최대한 많은 강의를 배정하려고 한다. 배정된 강의는 서로 겹치지 않아야 하며 수업시간의 길이와 상관없이 최대한 강의를 많이 배정하라. 단, 두 강의의 시작시간과 종료시간은 겹쳐도 된다.

제약조건

1 ≤ N ≤ 106 인 정수
1 ≤ Si ＜ Fi ≤ 109

입력형식

첫 번째 줄에 강의 개수 N이 주어진다. i + 1 (1 ≤ i ≤ N)번째 줄에는 i번째 강의의 시작 시간 Si와 종료 시간 Fi가 주어진다.

출력형식

첫 번째 줄에 최대 강의 수를 출력하라.

입력예제1

3 1 3 2 4 3 5

출력예제1

2

 

 

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

public class Main {

    public static void main(String[] args) {
      Scanner s = new Scanner(System.in);

      int N = s.nextInt(); // 강의 수
      int[][] times = new int[N][2]; // 강의별 시작/종료 시간

      for(int i=0; i<N; i++) {
        times[i][0] = s.nextInt();
        times[i][1] = s.nextInt();
      }

      // 그냥 단순한 알고리즘임.
      // 강의가 끝나는 시간 순으로 정렬한 다음 이어붙이면 끝.
      Arrays.sort(times, (a, b) -> {
        return a[1] - b[1];
      });

      // 첫 강의의 종료 시간 입력 및 첫 강의가 끝났으므로 answer는 1부터 시작
      int answer = 1;
      int now = times[0][1];
      
      for(int i=1; i<N; i++) {
        if(now <= times[i][0]) {
          answer++;
          now = times[i][1];
        }
      }

      System.out.println(answer);
    }
}