MeetingRooms2 [source code]

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

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

    public static void main(String[] args) {
        MeetingRooms2 tester = new MeetingRooms2();
        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));
    }
}

这个算法的核心还是类似的, 就是 sorting 换成了insertion sort来做了; 速度就不谈了, 134ms, 基本是垫底的速度;

/**

• 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