소프티어 강의실 배정

Softeer 강의실 배정 바로가기

문제 설명

강의의 수와 강의들의 시작시간과 끝 시간이 주어진다.

김교수가 가장 많은 강의를 하려고 한다. 강의들이 서로 겹치지 않아야하며 수업시간의 길이와 상관없이 최대한 많은 강의를 배정해라.

접근 방식

가장 강의를 많이 들을 수 있게끔, 즉 greedy하게 강의를 선택하면 된다.

단순하다. 끝나는 시간이 빠른거 부터 계속 고르면 된다.

1. 우선 강의리스트를 끝나는 시간을 기준으로, 오름차순으로 정렬해준다.
2. 강의리스트를 돌면서 현재 강의의 시작시간과 전 강의의 끝 시간이 겹치지 않으면 현재 강의를 배정하면된다.

코드

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


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());

        Node[] lectures = new Node[N];
        
        for(int i = 0; i < N; i++){
            String[] time = br.readLine().split(" ");
            lectures[i] = new Node(Integer.parseInt(time[0]), Integer.parseInt(time[1]));            
        }

        Arrays.sort(lectures);

        int answer = 0;
        int curTime = 0;

        for(Node lecture : lectures){
            if(lecture.start < curTime){
                continue;
            }else{
                answer++;
                curTime = lecture.end;
            }
        }
        
        System.out.println(answer);

    }
    
    static class Node implements Comparable<Node>{
        int start;
        int end;
        
        public Node(int start, int end){
            this.start = start;
            this.end = end;
        }
        
        public int compareTo(Node o){
            return this.end - o.end;
        }

    }

}

Disscussion

유명한 그리디 문제라서 그런지 금방 풀 수 있었다.!