MeetingRoomsOPT [source code]

public class MeetingRoomsOPT {
    public boolean canAttendMeetings(Interval[] intervals) {
        int[] starts = new int[intervals.length];
        int[] ends = new int[intervals.length];
        for (int i = 0; i < intervals.length; i++) {
            starts[i] = intervals[i].start;
            ends[i] = intervals[i].end;
        }

        Arrays.sort(starts);
        Arrays.sort(ends);
        for (int i = 1; i < starts.length; i++) {
            if (starts[i] < ends[i - 1]) {
                return false;
            }
        }
        return true;
    }

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

这个其实是最简单的解法, 4ms, 速度也是很好. 我本来是想到这个方法的, 但是后面突然又觉得不太对;
我当时没有采用这个方法的主要原因就是因为担心这里 input5这样的情况,

但是后来自己尝试举了几个例子, 好像就算这样的情况, 这个算法还是能够计算出来结果?
[ ]
[ ]
[ ]
不过这个结论是怎么想到的呢?
事实上, 我们如果从结论出发, 确实是这样, 如果最后我们的 intervals 能够满足这样的 layout, 那么单纯的把 starts 和 ends 分开 sort, 最后的结果是可以和这个no overlapping形成充要关系的;

花了一晚上的时间, 写出了一个严谨的证明过程, 记在 bear 上面, 也发表在 discussion 上面了. 这个算法可以说是告一段落了. 这个证明记录在这个文件的最后.

另外, discussion 上有人直接给 Interval 加了 compare 的API, 解决了这个问题:

public boolean canAttendMeetings(Interval[] intervals) {  
  if (intervals == null)  
    return false;  

  // Sort the intervals by start time  
  Arrays.sort(intervals, new Comparator<Interval>() {  
    public int compare(Interval a, Interval b) { return a.start - b.start; }  
  });  

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

  return true;  
}

这个用法我之前不太熟悉, 不过显然是可以的, 而且更加legitimate;

/**

• 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

Problem Description

Proof of correctness for 252.Meeting Rooms

Blog

Proof of Correctness

This algorithm is the first thought that came to my mind when I first saw this problem, but I later decided it not correct due to the pairing problem. But now that the OJ showed this solution actually right, I started thinking again the science behind this again.

If the intervals stays in the original pairing after sorting, e.g.: [1,2], [3,4], [5, 6], after sorting would be:

  
start end  
1      2  
3      4  
5      6  

  
start end  
0      2  
1      4  
3      6  

  
  [  ]  
      [  ]  
[          ]  

Lemma1: If the pairing for interval i is broken during the separate sorting, there must be another interval that completely contains interval i. Naturally, the right answer in this situation would be to return false.
Proof: suppose interval[i].start is at position m of the sorted starts array, and interval[i].end is at the position n of the sorted ends array. if m == n, then we know that the pairing is not broken for interval[i]. Otherwise, the pairing is broken for interval[i]. WLOG we suppose m > n, and we know that there are m intervals that starts before interval i starts, and there are n intervals that ends before interval i ends, and immediately we know that there are m - n intervals that starts earlier than interval i, but ends later than interval i. Actually, we only need the existence of one such overdue interval. This overdue interval starts earlier than interval i, and ends later than interval i, which implies that it completely comprehends interval i. This is clearly a situation that you can't attend both interval i and this overarching interval.
If m < n, then it's obvious that there be another m' and n' that belongs to the same interval i', and also having m' > n'. Because if e.g. 3 intervals started before interval i started, and 5 intervals ended before interval i ended, then there can only be at most 3 intervals that started before interval i and also ended before interval i ended. The 2 intervals left must have started after interval i have started, but also ended before interval i ended. These 2 intervals are the intervals with m' > n'. Interval i contains these two intervals in this case.
End of Proof

Let's clear up a little: we know that if no pairing is broken, this algorithm can determine the right result (true or false). We know that if any pairing is broken, the right answer should be false. But we do not know yet whether the algorithm can spit out false in such a scenario.

Lemma2: After sorting, for each position m, we have starts[m] <= ends[m]
Proof: The point is, we can't have starts[m] > ends[m] for any m = 0..length-1.
Suppose we do have starts[m] > ends[m]. Then we call the interval corresponding to ends[m] the interval k. We prove that interval k can't exist.
Since the arrays are sorted, the m - 1 intervals corresponding to ends[0]..ends[m-1] must all begin before starts[m]: they all ends before interval k, which ends at ends[m], and we also know that ends[m] < starts[m], which in turn means that all these m - 1 intervals all starts before starts[m] (because each interval starts before it ends). More graphically speaking, the m - 1 intervals corresponding to ends[0]..ends[m-1] must also all corresponds to starts[0]..starts[m-1] (although the order within may be broken).
Have this conclusion in hand, we know that there will be no way to arrange interval[k].start: it has to be within the first m - 1 entries of starts (because its start has to be smaller than ends[m], which is smaller than starts[m]), which are already all taken by the m - 1 intervals corresponding to ends[0]..ends[m-1]. Here we have the contradiction.
End of Proof

Lemma3: For interval i, if its start is at position m of the sorted starts array, and its end is at position n of the sorted ends array, then this algorithm (which compares each pair of consecutive intervals) will return false.
Proof:
First, let's suppose m > n:
If m = n + 1, then the proof is very easy: we would end up compare starts[n+1] with ends[n], which is comparing interval[i].start with interval[i].end (because again reminder: interval[i].start = starts[m], interval[i].end = ends[n]) , which will return less than, which will make the algorithm return false;
If m is arbitrarily larger than n, things get a little more complicated. We prove the lemma in this situation with contradiction. Suppose the algorithm actually returns true, this means the algorithm finds this conclusion: , for any i = 1..length-1, starts[i] >= ends[i-1].
Remind yourself that starts[m] = interval[i].start, ends[n] = interval[i].end;
We apply this conclusion to the range of i = n+1..m:

  
starts[n+1] >= ends[n]  
starts[n+2] >= ends[n+1]  
...  
starts[m] >= ends[m-1]  

  
starts[n+1] <= ends[n+1]="" starts[n+2]="" <="ends[n+2]" ...="" starts[m-1]="" pre="">
We easily have (by transitivity):  

  
starts[m] >= ends[n]  

  
interval[i].start >= interval[i].end  

 interval[i].start < interval[i].end

In the case of m < n, we have a similar symmetric proof as we did for the proof for lemma 1 (there must be some m' > n' for some interval i', and we apply the proof above to interval i').
End of Proof

I hope it's now clear when combining the three lemmas together, the correctness of this algorithm is elucidated. In my opinion, the algorithm looks deceptively simple, but thinking for the proof of correctness is quite fun.