[백준] 1374번 강의실 - Java

 

 

문제출저

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

1374번: 강의실

 

 

 

문제풀이

1. 리스트를 시작시간으로 정렬

2. 우선순위큐의 순서를 종료시간을 기준으로 오름차순 정렬(종료시간이 빠른 것부터 출력)

3. 리스트를 우선순위큐에 대입

4. 리스트의 시작시간보다 작은 종료시간을 배제

5. 마지막으로 큐에 남은 강의들의 갯수가 최소의 갯수이다.

 

 

 

소스코드

package studyGroup.july.july7;

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

public class 백준1374강의실 {

    static int n;
    static ArrayList<lecture> lecturelist;
    static int answer;

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        n = Integer.parseInt(br.readLine());

        lecturelist = new ArrayList<>();

        for(int i = 1; i <= n; i++)
        {
            StringTokenizer st = new StringTokenizer(br.readLine());

            int index = Integer.parseInt(st.nextToken());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());

            lecturelist.add(new lecture(index, start, end));
        }


        // 시작 순서로 정렬
        Collections.sort(lecturelist,  new Comparator<lecture>() {
            @Override
            public int compare(lecture o1, lecture o2)
            {
                return o1.start - o2.start;
            }
        });

        // 빨리 끝나는 강의부터 나오게 정렬
        PriorityQueue<lecture> que = new PriorityQueue<>(new Comparator<lecture>() {
            @Override
            public int compare(lecture o1, lecture o2) {
                return o1.end - o2.end;
            }
        });

//        PriorityQueue<Integer> que = new PriorityQueue<>();

        int answer = 0;


        // 이 부분이 중요했네
        // 비교한다음에 넣어야 했다

        for(int i = 0; i < n; i++)
        {
            while(!que.isEmpty() && que.peek().end <= lecturelist.get(i).start)
            {
                que.poll();
            }

            que.add(lecturelist.get(i));
            answer = Math.max(answer, que.size());
        }

        System.out.println(answer);

    }

    static class lecture
    {
        int index;
        int start;
        int end;

        lecture(int index, int start, int end)
        {
            this.index = index;
            this.start = start;
            this.end = end;
        }
    }

}