# Easy JAVA solution beat 98%

• ``````public boolean canAttendMeetings(Interval[] intervals) {
int len=intervals.length;
if(len==0){
return true;
}
int[]begin=new int[len];
int[]stop=new int[len];
for(int i=0;i<len;i++){
begin[i]=intervals[i].start;
stop[i]=intervals[i].end;
}
Arrays.sort(begin);
Arrays.sort(stop);
int endT=0;
for(int i=1;i<len;i++){
if(begin[i]<stop[i-1]){
return false;
}
}
return true;
}``````

• It works but I don`t quite understand this solution. Could you explain it? Thanks.

• overlap means there's an interval which start time is earlier than another's end time which begins before this one, e.g.: intervalA: start at time1, end at time5, intervalB: start at time4, end at time9, so this results in overlap. I sort the start time array and end time array to find if this happens

• nice solution. here is my another way:

``````public class Solution {
public boolean canAttendMeetings(Interval[] l) {
if (l.length < 2) return true;
Arrays.sort(l, new Comparator<Interval>(){
@Override
public int compare(Interval a, Interval b) {
return a.start - b.start;
}
});
for (int max = l[0].end, i = 1; i < l.length; i++) {
if (l[i].start == l[i - 1].start || l[i].start < max) return false;
max = Math.max(max, l[i].end);
}
return true;
}
}``````

• Only works when "si < ei" for each [si, ei] intervals.

If there are intervals where si == ei, may get wrong result.

For example, [[1,10],[5,5],[11,15]].

• there 2 condition which will overlap

1. the sorting order of begin is the same to stop, and the later meeting begins before the beginning of its previous one: [1,3], [2, 4], [5,7] --> false
2. begin[i] is paired with stop[i - 1], (by definition begin[i] < stop[i - 1] in the same pair) but this also means false. Because it means another meeting begins but not stop at this point. eg. [1,2], [3, 6], [4,5]

• @ZGeng not exactly, in your case, intervals [0, 5] and [5, 10] are also overlapped, but not for now. And this algorithm only needs to be adjusted a little bit.

• @printf_ll_
Sorry I still don't quite understand this solution.
Let's say we have [5,10] [15,20] [0,30] and we sort them, we get two arrays which are
{0, 5, 15} and {10, 20, 30}. Why can we know it's false if begin[i] < stop[i-1] (since it's out of sequence). Here we say 5<10 so it`s false. But actually 5 and 10 means same meeting [5,10]. Not sure if I miss something. Could you explain more? Thank you!

• we have [5,10] [15,20] [0,30] and we sort them, we get two arrays which are
{0, 5, 15} and {10, 20, 30}

if we can attend all the meetings, for the first start time"0", we should have an earlier end time than 10, rather than "30". E.g. It will become {0,5,15} and {3,10,20} with time slots [5,10], [15,20], and [0,3]. Now we can attend all meetings.

We can conclude that, if we want to attend all the meetings, we need to make sure that the next meeting's start time is later than previous end time.

• Why this is faster than the solution just sort the Intervals?

• nice solution. and c# version by your idea:

``````    public bool CanAttendMeetings(Interval[] intervals) {
int[] s = new int[intervals.Length];
int[] e = new int[intervals.Length];
int i = 0;
foreach(var item in intervals)
{
s[i] = item.start;
e[i++] = item.end;
}
Array.Sort(s);
Array.Sort(e);
i--;
while(i > 0)
{
if(s[i--] < e[i]) return false;
}
return true;
}``````

• # 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 incorrect due to the pairing problem. But now that the OJ accepted this solution, I started thinking again the science behind this.

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
```

the start and end of interval i all stayed in the ith position in array `starts` or `ends`. In this situation, what's left to do is easy to understand, just make sure no `start[i]` is smaller than `end[i-1`] for `i=1..length-1` is okay.

But the subtlety here is when the pairing is actually broken during the sorting.
E.g. if we have: [1,2], [3,4], [0, 6], then the sorting gives us:

```start end
0      2
1      4
3      6
```

The algorithm would still return false in this case, but only due to the fact like `1 < 2`, which only states the seemingly trivial fact of `intervals[0].start < intervals[0].end`. If we are trying to determine that no other interval begins before this interval stops, comparing 1, which is `interval[0].start`, to 2, which is `interval[1].end`, does not make any immediate sense.

Incidentally, to help understanding: if we visualize, we have something like:

```  [  ]
[  ]
[          ]
```

### Lemma 1

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 one same interval `i'`, and also satisfying `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/will spit out false in such a scenario.

### Lemma 2

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 by contradiction.
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).
Having 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

### Lemma 3

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]
```

and we aggregate all these `m - n` inequalities, together with the conclusion from Lemma 2:

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

We easily have (by transitivity):

```starts[m] >= ends[n]
```

Which means

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

Now, as long as the input is legal, we must have

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

for all `i`. Thus we have the contradiction.

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 that 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.

• @vegito2002

"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."

m includes intervals that starts before interval i starts, but not includes intervals that starts after interval i starts and before i ends. And since there are n intervals that ends before interval i ends, so, n might include some intervals that start later than i.

Suppose [1,2] [3,4],[5,6] [7,100] [8,99] [9 98]
Start: 1,2,3,5,6,7,8,9
End: 2,4,6,98,99,100
So, suppose m = 8, n = 3, m > n, and m - n = 5, but there are less 5 intervals that ends later than [9 98]
Thus, how can you interpret this: "immediately we know that there are m - n intervals that starts earlier than interval i, but ends later than interval I"

• @vegito2002

"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."

m includes intervals that starts before interval i starts, but not includes intervals that starts after interval i starts and before i ends. And since there are n intervals that ends before interval i ends, so, n might include some intervals that start later than i.

Suppose [1,2] [3,4],[5,6] [7,100] [8,99] [9 98]
Start: 1,2,3,5,6,7,8,9
End: 2,4,6,98,99,100
So, suppose m = 8, n = 3, m > n, and m - n = 5, but there are less 5 intervals that ends later than [9 98]
Thus, how can you interpret this: "immediately we know that there are m - n intervals that starts earlier than interval i, but ends later than interval I"

Hi, thanks for the reply, but I think you statement is not well-formated. In your example, you have 6 intervals, but you have 8 starts and 6 ends after sorting. Also, when you say `m=8`, it seems that you interprets `m` as 1-based, but when you say `n=3`, it looks like you are using 0-based again. It does not really matter whether you use 0-based or 1-based, but you have to pick one and apply it consistently to `m` and `n`. Can you please rephrase your opinion, exp. your example? It is kinda confusing to me now what your objection is.

If for `[1,2] [3,4],[5,6] [7,100] [8,99] [9 98]`, we actually have:

starts ends
1 2
3 4
5 6
7 98
8 99
9 100

And `[9,98]`, if 0-based, then we have `m=5, n = 3`, and `m-n=2`, meaning there are 2 intervals that starts before `[9,98]` and ends later than it: they are `[7,100]` and `[8,99]`. I don't see the problem here.

• @ZGeng it is(begin[i]<stop[i-1]). not stop[i]. Why would it be wrong?

• @Scarlett_comeup
"and the later meeting begins before the beginning of its previous one: "
I think beginning should be changed to ending.

• @vegito2002
Thanks for the explanation. And it is easier to prove the correctness of this algorithm by induction.
Given:
Start time sorted in ascending order: [S1, S2, S3, ... , Sn]
End time sorted in ascending order: [E1, E2, E3, ... , En]
We want to prove that if Si+1 > Ei, for i=0, 1, ...., n, then we will also have Ei > Si, for i=0,1, ..., n+1.

Base case:
If S1>E0, it is obvious that E1 > S1 and E0 > S0.

Hypothesis:
Assumes that given Si+1 >= Ei, for i=0, 1, ...., m, then Ei >= Si is true for i=0,1, ..., m + 1.

Induction:
We want to prove that given Si+1 >= Ei, for i=0, 1, ...., m + 1, then Ei >= Si is true for i=0,1, ..., m + 2, in which we only need to prove that Em+2 > Sm+2.

Prove by contradiction: If Em+2 < Sm+2, it means Sm+2 > Ej, j =0,1, m+2, which is not possible.

Hence the induction for all positive value of i.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.