[백준 알고리즘] 11000번 자바(Java) 강의실 배정

조건

문제

수강신청의 마스터 김종혜 선생님에게 새로운 과제가 주어졌다.

김종혜 선생님한테는 Si에 시작해서 Ti에 끝나는 N개의 수업이 주어지는데, 최소의 강의실을 사용해서 모든 수업을 가능하게 해야 한다. 

참고로, 수업이 끝난 직후에 다음 수업을 시작할 수 있다. (즉, Ti ≤ Sj 일 경우 i 수업과 j 수업은 같이 들을 수 있다.)

수강신청 대충한 게 찔리면, 선생님을 도와드리자!

 

입력

첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000)

이후 N개의 줄에 Si, Ti가 주어진다. (0 ≤ Si < Ti ≤ 109)

출력

강의실의 개수를 출력하라.

 

풀이

n의 최대수가 20만이고 시간제한 1초이므로 시간복잡도 O(nlogn)또는 O(n)만에 풀어야 하는 문제이다.

각 강의실 시작시간과 도착시간에 각각 +1 , -1을 이단배열에 대입 후 정렬시켜준다
이후에 정렬된 시간들을 순서대로 읽으며 강의가 시작되는 +1과 강의가 끝나는 -1을 더해준다.
읽는 와중에 최대로 강의가 진행되고 있는 시간에 강의수를 cnt하는 변수를 하나해준다.
최대cnt값이 답이다

결국은 한 강의가 몇시부터 몇시까지인지보다 강의시작시간이 1,2,3 이고 강의끝나는시간이 3,4,5이다 가 중요한거
강의 시작과 끝 조합이 중요한게 아니라 강의 시작묶음과 강의 끝나는 묶음이 중요하다

 

좀더 이해가 쉽도록 아래 사진으로 설명하겠다.

 

각 강의가 어떤식으로 배열로 들어가고 정렬 후모습이 어떤지 표현

 

 

 

예제 입력 예시

3
1 3
2 4
3 5

 

 

예제 출력 예시

2

 

소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

//11000번 강의실 배정

public class P11000
{
    public static void main(String args[]) throws IOException
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int cnt =0;    //강의 시작시+1, 종료시 -1
        int maxCnt = 0;   //최대 강의실 배정 수
        int[][] classS = new int[N*2][2];  //강의 시작시간 종료시간과, 그거에따른 수 대입(1또는 -1)
        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            classS[i*2][0] = Integer.parseInt(st.nextToken());
            classS[i*2][1] = 1;
            classS[i*2+1][0] = Integer.parseInt(st.nextToken());
            classS[i*2+1][1] = -1;
        }
        Arrays.sort(classS, new Comparator<int[]>() {  //정렬
            @Override
            public int compare(int[] o1, int[] o2) {
                if(o1[0]==o2[0]) return o1[1] - o2[1];   //강의시간이 같을 경우
                return o1[0] - o2[0];
            }
        });

        //정렬된 강의 배열 돌리기
        for (int[] s : classS) {
            cnt+= s[1];
            if(cnt > maxCnt) maxCnt = cnt;
        }

        //최대로 강의실 빌린 수 출력
        System.out.println(maxCnt);
    }
}

 

 

 

 

문제 출처

https://www.acmicpc.net/problem/11000

11000번: 강의실 배정