백준(BOJ) 1931 : 회의실배정 (JAVA)

문제링크 : https://www.acmicpc.net/problem/1931

1931번: 회의실배정

 

어떻게 하면 가장 적은 횟수의 비교를 통해 최댓값을 얻어낼 수 있을지를 생각해내는 게 중요한 문제이다. 필자는 처음에 정말 단순하게 '길이(Duration)가 짧은 회의부터 우선적으로 넣으면 되지 않을까?'라고 생각을 했으나, 이 경우에는 회의를 넣어도 되는지 판단하는 시점에서 이미 추가된 "모든" 회의들과 겹치는 부분이 없는지를 비교해야했다. 이 경우의 시간복잡도는 O(N^2)이다. 그러다 고민 끝에 길이따위는 중요하지 않고, 끝나는 시간만 생각하면 되겠구나!라는 걸 깨달았다. 긴~ 막대기가 있다고 생각해보자. 그 막대기에 최대한 많은 조각을 넣어야한다고 생각해보면, 왼쪽부터 작은거 순서대로 차근차근 넣어주면 된다. 코드는 아래와 같다.

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        Meeting[] meetings = new Meeting[n];
        
        for(int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            meetings[i] = new Meeting(start, end);
        }
        
        Arrays.sort(meetings);
        
        int cnt = 1;
        Meeting pastMeeting = meetings[0];
        
        for(int i = 1; i < n; i++) {
            Meeting meeting = meetings[i];
            
            if(!meeting.intersect(pastMeeting)) {
                cnt++;
                pastMeeting = meetings[i];
            }
        }
        
        System.out.println(cnt);
    }
    
    private static class Meeting implements Comparable<Meeting> {
        private int start;
        private int end;
        
        public Meeting(int start, int end) {
            this.start = start;
            this.end = end;
        }
 
        public int getStart() {
            return start;
        }
 
        public int getEnd() {
            return end;
        }
 
        @Override
        public int compareTo(Meeting obj) {
            return this.end - obj.getEnd();
        }
        
        public boolean intersect(Meeting obj) {
            return obj.getStart() < this.end && obj.getEnd() > this.start;
        }
    }
}

 

상위권 풀이들과 비교해보니, 어째 시간이 좀 더 길게 나왔다. 차이를 분석해보니, 굳이 겹치는(intersect) 여부를 보지 않고, 바로 이전의 end값과 비교시점의 start만 비교하면 되더라. 이 경우에는 오버라이드하는 함수 "compareTo" 에 조건이 일부 추가된다. 그 이유는 길이가 0인 회의들 때문이다. 코드는 아래와 같다.

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        Meeting[] meetings = new Meeting[n];
        
        for(int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            meetings[i] = new Meeting(start, end);
        }
        
        Arrays.sort(meetings);
        
        int cnt = 1;
        int cursor = meetings[0].getEnd();
        
        for(int i = 1; i < n; i++) {
            Meeting meeting = meetings[i];
            
            if(meeting.getStart() >= cursor) {
                cnt++;
                cursor = meeting.getEnd();
            }
        }
        
        System.out.println(cnt);
    }
    
    private static class Meeting implements Comparable<Meeting> {
        private int start;
        private int end;
        
        public Meeting(int start, int end) {
            this.start = start;
            this.end = end;
        }
 
        public int getStart() {
            return start;
        }
 
        public int getEnd() {
            return end;
        }
 
        @Override
        public int compareTo(Meeting obj) {
            int ret = this.end - obj.getEnd();
            
            if(ret == 0) {
                ret = this.start - obj.getStart();
            }
            
            return ret;
        }
    }
}