[문제풀이] 09-02. 회의실 배정

인프런, 자바(Java) 알고리즘 문제풀이

Greedy Alogorithm - 0902. 회의실 배정

🗒️ 문제

🎈 나의 풀이

	private static class Time implements Comparable<Time> {
        int start, end;

        public Time(int start, int end) {
            this.start = start;
            this.end = end;
        }

        @Override
        public int compareTo(Time o) {
            if(this.end == o.end) return Integer.compare(this.start, o.start);
            return Integer.compare(this.end, o.end);
        }
    }

    private static int solution(List<Time> list) {
        int answer = 0;
        Collections.sort(list);

        int endTime = 0;
        for (Time t : list) {
            if (t.start >= endTime) {
                endTime = t.end;
                answer++;
            }
        }

        return answer;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        List<Time> list = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            int start = sc.nextInt();
            int end = sc.nextInt();
            list.add(new Time(start, end));
        }

        System.out.println(solution(list));
    }

🖍️ 강의 풀이

  class Time implements Comparable<Time>{
      public int s, e;
      Time(int s, int e) {
          this.s = s;
          this.e = e;
      }
      @Override
      public int compareTo(Time o){
          if(this.e==o.e) return this.s-o.s;
          else return this.e-o.e;
      }
  }

  class Main {
      public int solution(ArrayList<Time> arr, int n){
          int cnt=0;
          Collections.sort(arr);
          int et=0;
          for(Time ob : arr){
              if(ob.s>=et){
                  cnt++;
                  et=ob.e;
              }
          }
          return cnt;
      }

      public static void main(String[] args){
          Main T = new Main();
          Scanner kb = new Scanner(System.in);
          int n=kb.nextInt();
          ArrayList<Time> arr = new ArrayList<>();
          for(int i=0; i<n; i++){
              int x=kb.nextInt();
              int y=kb.nextInt();
              arr.add(new Time(x, y));
          }
          System.out.println(T.solution(arr, n));
      }
  }

💬 짚어가기

해당 문제는 Greedy Algorithm를 이용하여 풀 수 있다. 이 문제를 해결하는 키는
회의 종료 시간이 빠른 순으로 배정하는 것이다.

이 때, 정렬 기준으로 종료 시간이 같은 경우 시작 시간이 빠른 것을 우선으로 하는 것이
포인트이다.