[백준] no1931: 회의실 배정

문제

N가지의 회의 시작시간-종료시간 세트가 주어진다.

회의를 최대한 많이 잡을 수 있는 경우를 구하시오

회의의 수 N(1 ≤ N ≤ 100,000)

시작 시간과 끝나는 시간은 2^31-1보다 작거나 같은 자연수 또는 0

 

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

---

원리

종료시간을 기준으로 계산

: 선택할 수 있는 시간이 많아지려면, 같은 활동시간 안에서 종료시간이 더 빠르면 된다.

* 종료시간이 같은 경우, 시작시간이 빠른 순으로 정렬해야한다

---

풀이방법

1. 입력된 회의를 객체화하여 List에 담는다.

2. 리스트의 각 요소(Meeting)을 '끝나는 시간 순 -> 시작하는 시간 순'으로 정렬

3. 리스트를 순회하며 남은 회의중 끝나는 시간이 가장 빠른 회의의 끝나는 시간을 기록(현재회의)

4. 현재 회의의 끝나는 시간과 같거나 더 나중인 시작시간이 있으면 해당 회의를 새로 시작하고,

    해당 회의의 끝나는 시간을 저장하며, 회의 count + 1

---

나의 코드

1. BFS를 이용한 방법

: 생각해보니 DFS가 더 맞을거 같은 느낌

: 제일 빠른 start 시간의 스케쥴을 꼭 골라야 하는 경우가 아닐수 있음을 간과했다.

* 의문점 : 배열의 최대길이는 이론상 2,147,483,647가 될 것인데, 정작 실행하면 메모리 초과 오류가 발생한다

Exception in thread "main" java.lang.OutOfMemoryError: Requested array size exceeds VM limit

import java.io.*;
import java.util.*;
import java.util.stream.Collectors;

public class no1931 {

    static ArrayList<Factor> list;
    static List<Factor> sortedList;

    static class Factor {
        private int start;
        private int end;
        public Factor(int start, int end) {
            this.start = start;
            this.end = end;
        }
        public int getStart() { return this.start; }
        public int getEnd() { return this.start; }

    }

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

        int T = Integer.parseInt(br.readLine());
        list = new ArrayList<>();

        for(int i=0; i<T ; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            Factor factor = new Factor(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
            list.add(factor);
        }
        Comparator<Factor> compare = Comparator.comparing(Factor::getStart).thenComparing(Factor::getEnd);
        sortedList = list.stream().sorted(compare).collect(Collectors.toList());

        System.out.println(BFS());
    }

    private static int BFS () {
        PriorityQueue<Factor> queue = new PriorityQueue<>((a,b) -> a.getStart() - b.getStart());
        int[] visited = new int[214748364]; // 회의끝의 마지노선 2^31-1

        Factor first = sortedList.get(0);
        queue.add(first);
        visited[first.getEnd()] = 1;
        sortedList.remove(0);

        while(!queue.isEmpty()) {

            Factor now = queue.poll();

            if(sortedList.size()==0) return visited[now.getStart()]+1;

            for(int i = 0; i<sortedList.size(); i++) {
                if (now.getEnd() > sortedList.get(i).getStart()) sortedList.remove(i);
                else {
                    queue.add(sortedList.get(i));
                    visited[sortedList.get(i).getStart()] = now.getEnd()+1;
                    sortedList.remove(i);
                }
            }
        }
        return 0;
    }
}

2. 모든 경우의 수를 구하는 방법 [시간초과]

static ArrayList<Factor> list;
static List<Factor> sortedList;

static class Factor {
    private int start;
    private int end;
    public Factor(int start, int end) {
        this.start = start;
        this.end = end;
    }
    public int getStart() { return this.start; }
    public int getEnd() { return this.end; }

}

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

    int T = Integer.parseInt(br.readLine());
    list = new ArrayList<>();

    for(int i=0; i<T ; i++) {
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        Factor factor = new Factor(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
        list.add(factor);
    }
    Comparator<Factor> compare = Comparator.comparing(Factor::getStart).thenComparing(Factor::getEnd);
    sortedList = list.stream().sorted(compare).collect(Collectors.toList());

    int max = 0;

    for(int i = 0 ; i < sortedList.size() ; i++ ){
        Factor now = sortedList.get(0);
        int cnt = 1;
        for(int j = 1 ; j < sortedList.size() ; j++) {
            Factor after = sortedList.get(j);
            if(now.getEnd()<after.getStart()) {
                now = sortedList.get(j);
                cnt++;
            }
            if(now.getStart()==after.getStart() && now.getEnd()>after.getEnd()) now = after;
        }
        if(cnt>max) max = cnt;
    }

    System.out.println(max);
}

 

3. 종료순 정렬

import java.io.*;
import java.util.*;
import java.util.stream.Collectors;

public class no1931 {

    /**
     * 입력되는 각 회의 : 시작시간 | 종료시간을 가지고 있음
     */
    static class Meeting {
        private int start;
        private int end;
        public Meeting(int start, int end) {
            this.start = start;
            this.end = end;
        }
        public int getStart() { return this.start; }
        public int getEnd() { return this.end; }
    }

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

        int T = Integer.parseInt(br.readLine());
        List<Meeting>list = new ArrayList<>();  // 각 미팅을 담을 리스트
        for(int i=0; i<T ; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            Meeting meeting = new Meeting(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
            list.add(meeting);
        }

        /**
         * 미팅을 정렬 : 끝나는 시간을 기준으로 정렬 -> 시작시간이 빠른 순으로 정렬
         */
        Comparator<Meeting> compare = Comparator.comparing(Meeting::getEnd).thenComparing(Meeting::getStart);
        List<Meeting> sortedList = list.stream().sorted(compare).collect(Collectors.toList());

        /**
         * 끝나는 시간은 0시부터 다음 회의가 배정될때마다 해당 회의의 끝나는 시간으로 갱신될 것임
         */
        int count = 0;
        int endTime = 0;
        for(int i = 0 ; i < sortedList.size() ; i++) {
            if(endTime<=sortedList.get(i).getStart()) {
                endTime = sortedList.get(i).getEnd();
                count++;
            }
        }
        
        System.out.println(count);
    }
}

---

레퍼런스 코드

참고 링크 : https://myeongju00.tistory.com/29