Blind 75 Must do Leetcode: Meeting Rooms

Blind75는 Leetcode의 문제들 중 소프트웨어 엔지니어 인터뷰 준비에 유용한 75개의 문제를 선정한 것을 말한다. Blind75는 배열, 문자열, 링크드 리스트, 트리, 그래프, 정렬, 다이나믹 프로그래밍 등 다양한 알고리즘과 자료구조를 포함하고 있다. 따라서 이 목록은 인터뷰 준비를 체계적으로 하고자 하는 사람들에게 방향을 제시해 주며, 실제 인터뷰에서 자주 출제되는 유형의 문제들을 연습할 수 있게 해 준다.

 

Blind 75 문제를 하루에 한 문제씩 풀어보면서 코딩 테스트 감을 유지해보려고 한다. Blind 75 풀어보기 시리즈 네번째 문제는 Meeting Rooms다. https://leetcode.com/problems/meeting-rooms

LeetCode - The World's Leading Online Programming Learning Platform

이 문제는 미팅의 시작 시간과 끝나는 시간을 담은 배열의 배열(이차원 배열)인 interval을 모두 참석할 수 있는지 여부를 반환하는 것이다. 예제를 보면 문제를 더 잘 이해할 수 있으니 예제를 보자.

Input: intervals = [[0,30],[5,10],[15,20]]
Output: false

Input: intervals = [[7,10],[2,4]]
Output: true

 

첫 번째 예제에서 첫 번째 미팅과 두 번째 미팅의 시간이 겹치기 때문에 결과가 false이고, 두 번째 예제에서는 미팅 시간이 겹치지 않기 때문에 결과가 true이다. 즉, 주어진 배열에 들어있는 미팅 시간 중에 겹치는 시간이 없다면 결과는 true이고, 하나라도 겹친다면 결과는 false가 된다고 이해할 수 있다.

미팅 시간이 겹치는 경우가 있는지 단순히(brute-force) 전부 비교를 한다면 n개의 미팅이 있을 때 O(n^2) 시간이 걸린다. 더 빠르게 답을 구할 수 있는 방법이 있을까? interval 배열을 정렬하면 어떨까? 배열을 정렬하면 미팅 시간을 비교할 때 바로 다음 미팅 시간과 겹치는지만 비교하면 된다.

Arrays.sort 메소드를 이용해서 intervals를 정렬한다. 정렬 기준은 미팅의 시작 시간을 기준으로 오름차순 정렬한다. 그리고 미팅 시간을 순회하면서 다음 미팅 시간과 겹치는지 비교한다. 만약 겹치는 구간이 있다면 false를 바로 반환하고, 없다면 루프를 전부 순회한 뒤에 true를 반환한다.

class Solution {
    public boolean canAttendMeetings(int[][] intervals) {
        Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
        for(int i=0; i<intervals.length-1; i++) {
            if (intervals[i][1] > intervals[i+1][0]) {
                return false;
            }
        }
        return true;
    }
}

 

이 알고리즘의 시간 복잡도는 배열의 정렬에 O(nlogn) 그리고 루프 순회에 O(n)이 걸린다. 따라서 O(nlogn + n) = O(nlogn)이다. 그리고 공간 복잡도는 O(1)이다.

 

Blind75 포스팅 모음 https://codeendeavor.tistory.com/tag/blind75