MeetingRooms3 [source code]

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

    public void selectionSort(Interval[] intervals) {
        for (int i = 0; i < intervals.length; i++) {
            int min = i;
            for (int j = i + 1; j < intervals.length; j++) {
                if (intervals[j].start < intervals[min].start) min = j;
            }
            Interval tmp = intervals[min];
            intervals[min] = intervals[i];
            intervals[i] = tmp;
        }
    }

    public static void main(String[] args) {
        MeetingRooms3 tester = new MeetingRooms3();
        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),
        };
        tester.selectionSort(input4);
        for (Interval i : input4) System.out.print(i.start + " ");
        System.out.println();
    }
}

insertionSort依赖的 swap 太多了, 最后速度惨不忍睹. 看看用没有 swap 的版本的 insertionSort 能不能快一点;

不行, 就算是non-swap版本的 insertion sort其实并没有办法加速, 因为在找到插入位置之后, 还是要做 shift.
干脆使用selection sort;

不行, 速度还是很慢, 比之前的那个还要慢了, 139ms;

/**

• 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