MeetingRoomsOPT2 [source code]

public class MeetingRoomsOPT2 {
    public boolean canAttendMeetings(Interval[] intervals) {
        if (intervals.length <= 1) return true;
        sortOnStart(intervals, 0, intervals.length - 1);

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

    private void sortOnStart(Interval[] inter, int lo, int hi) {
        if (lo >= hi) return;

        int i = lo;
        int j = hi;
        int pivot = inter[lo + (hi - lo) / 2].start;
        while (i <= j) {
            while (inter[i].start < pivot) i++;
            while (inter[j].start > pivot) j--;
            if (i <= j) {
                Interval temp = inter[i];
                inter[i] = inter[j];
                inter[j] = temp;
                i++;
                j--;
            }
        }   

        if (lo < j) sortOnStart(inter, lo, j);
        if (i < hi) sortOnStart(inter, i, hi);
    }

    public static void main(String[] args) {
        MeetingRoomsOPT2 tester = new MeetingRoomsOPT2();
        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),
        };
        Interval[] input4 = {
            new Interval(0,3),
            new Interval(1,4),
            new Interval(3,6),
            new Interval(5,8),
            new Interval(2,5),
            new Interval(4,7),
            new Interval(6,9),
        };
        System.out.println(tester.canAttendMeetings(input3));
    }
}

这个是 submission 最优解, 3ms, 99%;
问了一下 guoye, 这个是quicksort, 不过是一个inplace splitting的版本;

这个算法刚开始没看懂其实是因为这里的 split 的过程其实是一个 inplace 的 split. 而且这个 inplace 的 split 跟 CLRS 上的做法不太一样. CLRS 上面的做法实际上还稍微复杂一些, L 和 G 之间的分界线是一直在变化的. 这里这个方法更加简单直接: 就用 mid 作为分界线, 然后你写 loop 的时候记住, mid 的左边的invariant 是始终只保留 L, 也就是比 pivot 小的 element, mid 右边的只保留G里面的内容. 而保证这个 invariant 的具体操作就是 swap.

幸亏在 submission 里面找了一下最优解, 不然还真的没有学到这么好的一个算法; g4g 上面的 partition 其实用的也是 CLRS 书上那个做法.

/**

• 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