[LeetCode/EASY] 252. MeetingRooms (JAVA) : 문제&풀이

 

 

회의실 예약 시간(interval)이 유효한지를 알아보는 문제이다.

 

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

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

 

Problem :

class Interval{
    int start;
    int end;

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

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

public class MeetingRooms {
    public boolean solve(Interval[] intervals) {

    }
}

 

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

 

Solution :

1. 매개변수로 들어오는 Interval 배열을 오름차순으로 정렬한다.
2. 정렬된 배열을 순차대로 돌며 한 회의시간이 끝나는 시간(end)과 다음 회의시간의 시작시간(start)을 비교하여 시간이 겹치지 않는지 확인한다.

class Interval{
    int start;
    int end;

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

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

public class MeetingRooms {

    // time complexity : Arrays.sort() using Dual-pivot Quicksort algorithm -> O(nlog(n))
    // space complexity : no additional space allocated -> O(1)
    public boolean solve(Interval[] intervals) {
        if (intervals == null) return false;

        // sort
        Arrays.sort(intervals, (o1, o2) -> o1.start - o2.start); // negative = ASC

        // compare
        for(int i = 1; i < intervals.length; i++){
            if (intervals[i-1].end > intervals[i].start){
                return false;
            }
        }
        return true;
    }
}

* Arrays.sort()는 QuickSort를 사용하며 배열을 정렬할 때 성능이 좋은 반면, (unstable)

  Collections.sort()는 TimeSort(MergeSort+InsertSort)를 사용하며 Object를 정렬하기 좋다. (stable)

 

* Arrays.sort()에서 Interval의 비교를 위해 Comparator의 compare를 override할 때

  return 값이 양수이면 내림차순(DESC), 음수이면 오름차순(ASC)이다.

 

Complexity : 

• 시간복잡도 (Time Complexity)
  • Dual-pivot QuickSort Algorithm을 사용하는 Arrays.sort()에 따라 O(n log n)
• 공간복잡도 (Space Complexity)
  • 추가적으로 할당한 공간이 없으므로 O(1)

 

Sample(Test) :

import java.util.Arrays;

class Interval{
    int start;
    int end;

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

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

public class MeetingRooms {

    public static void main (String args[]){
        Interval interval1 = new Interval(10, 30);
        Interval interval2 = new Interval(0, 20);
        Interval interval3 = new Interval(30, 50);
        Interval[] intervals = {interval1, interval2, interval3};

        MeetingRooms meetingRoom = new MeetingRooms();
        System.out.println(meetingRoom.solve(intervals));
    }

    // time complexity : Arrays.sort() using Dual-pivot Quicksort algorithm -> O(nlog(n))
    // space complexity : no additional space allocated -> O(1)
    public boolean solve(Interval[] intervals) {
        if (intervals == null) return false;

        // sort
        Arrays.sort(intervals, (o1, o2) -> o1.start - o2.start); // negative = ASC
        // compare
        for(int i = 1; i < intervals.length; i++){
            if (intervals[i-1].end > intervals[i].start){
                return false;
            }
        }
        return true;
    }
}

 

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

false