백준 1931번: 회의실 배정

풀이1

회의시간을 key, 회의시간에 해당되는 회의들을 value값으로 갖는 해시맵을 만든 뒤 짧은 key 값부터 꺼내오면서 배정했다.

결과: 시간 초과

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.lang.reflect.Array;
import java.util.*;

public class Problem1931 {

    static int totalMeeting;
    static HashMap<Long, ArrayList<long[]>> meetings = new HashMap<>();
    //배정에 쓸 arraylist
    static ArrayList<long[]> assign = new ArrayList<>();

    //arraylist를 매개변수로 받아 회의들이 배정 가능한지 확인하고 assign 변수 갱신
    public static void comp(ArrayList<long[]> meeting){
        for(long[] met : meeting){
            if(assign.isEmpty()){
                assign.add(met);
            } else {
                long[] front = new long[]{Long.MIN_VALUE, Long.MIN_VALUE, -1}; //맨 뒤의 값은 idx
                long[] back = new long[]{Long.MAX_VALUE, Long.MAX_VALUE, -1};
                for(int idx = 0; idx < assign.size(); idx++){
                    //맨 앞에 추가 가능
                    if(assign.get(0)[0]>=met[1]){
                        assign.add(0, met);
                        break;
                    } else if (assign.get(assign.size()-1)[1]<=met[0]){ //맨 뒤에 추가 가능
                        assign.add(met);
                        break;
                    }
                    if(assign.get(idx)[1]<=met[0] && front[1]<=assign.get(idx)[1]){
                        long[] temp = new long[]{assign.get(idx)[0], assign.get(idx)[1], idx};
                        front = temp.clone(); //깊은 복사
                    }
                    if(back[0] > met[1] &&assign.get(idx)[0]>=met[1] && back[0]>=assign.get(idx)[0]){
                        long[] temp = new long[]{assign.get(idx)[0], assign.get(idx)[1], idx};
                        back = temp.clone();
                    }
                }

                //배정가능
                if(front[0]!=Long.MIN_VALUE && back[0]!=Long.MAX_VALUE){
                    if((back[2]-1)!=front[2]){
                        if(met[0]>=front[1] && met[1]<=back[0] && assign.get((int)(back[2]-1))[0]>=met[1]){
                            assign.add((int)front[2]+1, met);
                        }
                    } else {
                        if(met[0]>=front[1] && met[1]<=back[0]){
                            assign.add((int)front[2]+1, met);
                        }
                    }

                }


            }
        }
    }


    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s = br.readLine();
        StringTokenizer st = new StringTokenizer(s, " ");
        totalMeeting = Integer.parseInt(st.nextToken());

        for(int i = 0; i < totalMeeting; i++){
            String met = br.readLine();
            StringTokenizer eachMet = new StringTokenizer(met, " ");
            long startTime = Integer.parseInt(eachMet.nextToken());
            long endTime = Integer.parseInt(eachMet.nextToken());

            if(meetings.containsKey(endTime-startTime)){
                ArrayList<long[]> temp = meetings.get(endTime - startTime);
                temp.add(new long[]{startTime, endTime});
                meetings.put(endTime - startTime, temp);
            } else {
                ArrayList<long[]> temp = new ArrayList<>();
                temp.add(new long[]{startTime, endTime});
                meetings.put(endTime - startTime, temp);
            }
        }

        //key정렬을 위한 arraylist
        ArrayList<Long> arySort = new ArrayList<>();
        Set set = meetings.keySet();
        Iterator iterator = set.iterator();
        while(iterator.hasNext()){
            long key = (long)iterator.next();
            arySort.add(key);
        }
        Collections.sort(arySort);

        for(long i : arySort){
            comp(meetings.get(i));
        }

        System.out.println(assign.size());

    }
}

시간복잡도가 key의 수와 key에 속한 value값에 따라 달라지는데, 최선의 경우가 'n'이기 때문에 key값의 구성에 따라 더 나빠질 수 밖에 없다.

풀이2

풀이 출처

https://st-lab.tistory.com/145

종료 시간을 기준으로 정렬한 뒤 종료 시간이 짧은 것부터 배정.
종료 시간이 같은 경우는 시작 시간이 빠른 순대로 정렬.

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




public class Problem1931_2 {


    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s = br.readLine();


        //회의의 수
        int totalMeeting = Integer.parseInt(s);

        //회의의 시작과 종료시간을 담을 배열
        int[][] meeting = new int[totalMeeting][2];

        for(int i = 0; i < totalMeeting; i++){
            String met = br.readLine();
            StringTokenizer st = new StringTokenizer(met, " ");
            //시작시간
            meeting[i][0] = Integer.parseInt(st.nextToken());
            meeting[i][1] = Integer.parseInt(st.nextToken());

        }

        //compare재정의, 정렬
        Arrays.sort(meeting, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {

                //종료 시간이 같은 경우 시작시간 순으로 정렬
                if(o1[1]==o2[1]){
                    return o1[0] - o2[0];
                }
                return o1[1] - o2[1];
            }
        });

        int answer = 0;
        int endTime = 0;
        for(int i = 0; i < totalMeeting; i++){
            if(meeting[i][0]>=endTime){
                answer++;
                endTime = meeting[i][1];
            }
        }

        System.out.println(answer);


    }
}