MeetingRooms [source code]

public class MeetingRooms {
    public boolean canAttendMeetings(Interval[] intervals) {
        sort(intervals);
        for (int i = 0; i < intervals.length - 1; i++) {
            if (intervals[i].end > intervals[i + 1].start) return false;
        }
        return true;
    }

    public void sort(Interval[] intervals) {
        int mid = intervals.length / 2;
        mergeSort(intervals, 0, intervals.length - 1);
    }

    private void mergeSort(Interval[] intervals, int l, int r) {
        if (l == r) return;
        int m = l + (r - l) / 2;
        mergeSort(intervals, l, m);
        mergeSort(intervals, m + 1, r);
        merge(intervals, l, m, r);
    }

    private void merge(Interval[] intervals, int l, int m, int r) {
        Interval[] L = new Interval[m - l + 2];
        Interval[] R = new Interval[r - m + 1];
        L[L.length - 1] = new Interval(Integer.MAX_VALUE, 0);
        R[R.length - 1] = new Interval(Integer.MAX_VALUE, 0);
        for (int i = 0; i < L.length - 1; i++) L[i] = intervals[l + i];
        for (int i = 0; i < R.length - 1; i++) R[i] = intervals[i + m + 1];
        int p1 = 0;
        int p2 = 0;
        for (int i = l; i <= r; i++) {
            if (L[p1].start <= R[p2].start) intervals[i] = L[p1++];
            else intervals[i] = R[p2++];
        }
    }

    public static void main(String[] args) {
        MeetingRooms tester = new MeetingRooms();
        Interval[] input1 = {
            new Interval(0, 30),
            new Interval(5, 10),
            new Interval(15, 20),
        };
        Interval[] input2 = {
            new Interval(5, 8),
            new Interval(6, 8),
        };
        Interval[] input3 = {
            new Interval(1,2),
            new Interval(3,4),
            new Interval(6,8),
        };
        System.out.println(tester.canAttendMeetings(input3));
    }
}

这个算法本身是对的, 思路也很简单, 根据 start 把所有的interval 都 sort 一遍, 然后顺序过一遍, 保证没有任何一个 interval 和自己的 successor overlap 就行了;
难点在于要自己实现一个 sorting, 因为这里的 element 是 interval, 而这个是没有实现 compareTo API 的.

我这里的选择是实现 mergesort, 不过最后没有过, stack overflow. 看来对于recursion 深度有限制. 下一步决定干脆就用 insertion sort 来实现算了. 然后后面看答案看别人是怎么做的;

另外自己不试一下不知道, 原来写一个 mergesort 都这么费劲;

所有的操作的返回值都选择 void, 这样避免讲 array 不停的传递, 浪费时间;

刚开始看错题目了, 以为是要判断是否一个人能够同时 attend 所有的 meeting, 这个就是要判断是否所有的 interval 都有一个共同的 overlapping 了;
这个是当时写的代码:

public boolean canAttendMeetings(Interval[] intervals) {  
    int maxS = 0, minE = Integer.MAX_VALUE;  
    for (Interval i : intervals) {  
        if (i.start > maxS) maxS = i.start;  
        if (i.end < minE) minE = i.end;  
    }  
    if (minE < maxS) return false;  
    return true;  
}

注意, 这里把最后minE < maxS这里negate 一下, 不能得到题目的答案! 我这个代码判断的是all overlap, 取反之后是not all overlap, 而题目要求的是all not overlap, 这个不是一个概念;

思考问题的时候, 很多时候你要做的是考虑怎么在正确的条件下做正确的事情, 要达到这个目的, 你要做的就是要使用差异思考的模式. 比如, 如果你这个代码要判断一个情形, 你除了要确定你这个代码能够判断你 intended 的这个情形, 还要举出一个不是你intended 的这个情形, 然后保证你的代码能够say no to this condition;

另外 interval 类的问题很常见, 脑子里思考的时候, 常见的 visualization 可以是:
[ ]
[ ]
[ ]
比如这样的, 就是一个no overlapping的情形;
[ ]
[ ]
[ ]
这样的, 就是有 overlapping 的情形;

in place merge sort 我查了一下, 好像特别难做, 所以我这里的 mergesort 直接就用最普通的方法实现了;

/**

• Definition for an interval.
• public class Interval {
• int start;
• int end;
• Interval() { start = 0; end = 0; }
• Interval(int s, int e) { start = s; end = e; }
• }
  */

Problem Description

Given an array of meeting time intervals consisting of start and end times [[s1,e1],[s2,e2],...] (si < ei), determine if a person could attend all meetings.

For example,
Given [[0, 30],[5, 10],[15, 20]],
return false.

Difficulty:Easy
Category:Algorithms
Acceptance:46.78%
Contributor: LeetCode
Companines
Facebook
Related Topics
sort
Similar question
Merge Intervals Meeting Rooms II