[LeetCode/MEDIUM] 253. Meeting Rooms II (JAVA) : 문제&풀이

 

 

필요한 최소한의 회의실 수를 구하는 문제이다.

 

인스턴스변수 start, end를 가진 Interval 클래스와

Interval 배열을 매개변수로 받는 solve 메서드의 틀이 주어진다.

 

Problem :

class Interval {
    int start;
    int end;

    Interval() {
        start = 0;
        end = 0;
    }

    Interval(int s, int e) {
        start = s;
        end = e;
    }
}

public class MeetingRoom2 {
    public int solve(Interval[] intervals) {

    }
}

풀이는 solve에 작성하면 된다.

 

Solution :

1. Interval 객체들이 담긴 intervals 배열을 시작 시간 오름차순으로 정렬한다.
2. 종료 시간 오름차순으로 하는 PriorityQueue를 생성한다.
3. intervals 배열을 순서대로 돌며
   1. PriorityQueue에 있는 가장 빨리 끝나는 회의가 이번 Interval의 시작시간과 같거나 먼저 끝나면 PriorityQueue의 가장 빨리 끝나는 회의를 제거한다. (두 회의를 같은 회의실에서 진행할 수 있으므로 1개의 회의실만 필요하다는 의미)
   2. PriorityQueue에 이번 Interval을 추가한다.
4. PriorityQueue의 크기(=총 필요한 회의실 수)를 반환한다.

import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Queue;

class Interval {
    int start;
    int end;

    Interval() {
        start = 0;
        end = 0;
    }

    Interval(int s, int e) {
        start = s;
        end = e;
    }
}

public class MeetingRoom2 {

    // time complexity : priorityQueue sort -> O(n log n)
    // space complexity : priorityQueue<Interval> (copy of array 'intervals') -> O(n)
    public int solve(Interval[] intervals) {

        // sort by start time
        Arrays.sort(intervals, (a, b) -> a.start - b.start); // ASC

        // priorityQueue based on end time (to check the available meeting room)
        Queue<Interval> endtimeQueue = new PriorityQueue<>((a, b) -> a.end - b.end); // ASC

        // compare
        for (Interval interval : intervals) {
            if (!endtimeQueue.isEmpty() && endtimeQueue.peek().end <= interval.start) {
                endtimeQueue.poll();
            }
            endtimeQueue.offer(interval);
        }

        return endtimeQueue.size();
    }
}

 

이해하기 쉽게 그림으로 표현하면 다음과 같다.

 

Complexity :

• 시간복잡도 (Time Complexity)
  • PriorityQueue sort에 따라 O(n log n)
• 공간복잡도 (Space Complexity)
  • 매개변수 intervals만큼 담아둘 PriorityQueue사용에 따라 O(n)

 

Sample(Test) :

import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Queue;

class Interval {
    int start;
    int end;

    Interval() {
        start = 0;
        end = 0;
    }

    Interval(int s, int e) {
        start = s;
        end = e;
    }

    @Override
    public String toString() {
        return "String.Interval { start = " + start + ", end = " + end + " }";
    }
}

public class MeetingRoom2 {

    // time complexity : priorityQueue sort -> O(n log n)
    // space complexity : priorityQueue<Interval> (copy of array 'intervals') -> O(n)
    public int solve(Interval[] intervals) {

        // sort by start time
        Arrays.sort(intervals, (a, b) -> a.start - b.start); // ASC

        // priorityQueue based on end time (to check the available meeting room)
        Queue<Interval> endtimeQueue = new PriorityQueue<>((a, b) -> a.end - b.end); // ASC

        // compare
        for (Interval interval : intervals) {
            if (!endtimeQueue.isEmpty() && endtimeQueue.peek().end <= interval.start) {
                endtimeQueue.poll();
            }
            endtimeQueue.offer(interval);
        }

        return endtimeQueue.size();
    }

    public static void main(String[] args) {
        Interval[] intervals = new Interval[]{
                new Interval(15, 25),
                new Interval(0, 30),
                new Interval(5, 15),
                new Interval(20, 30)
        };

        MeetingRoom2 m = new MeetingRoom2();
        System.out.println(m.solve(intervals));
    }
}

 

위 테스트 코드를 실행한 결과는 다음과 같다.

3