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[i1]){
return false;
}
}
return true;
}
Easy JAVA solution beat 98%


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; } }

there 2 condition which will overlap
 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
 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]
hope this help you :)

@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[i1] (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!

@sshen8734 said in Easy JAVA solution beat 98%:
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.

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
orends
. In this situation, what's left to do is easy to understand, just make sure nostart[i]
is smaller thanend[i1
] fori=1..length1
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 ofintervals[0].start < intervals[0].end
. If we are trying to determine that no other interval begins before this interval stops, comparing 1, which isinterval[0].start
, to 2, which isinterval[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 intervali
. Naturally, the right answer in this situation would be to return false.
Proof: supposeinterval[i].start
is at positionm
of the sortedstarts
array, andinterval[i].end
is at the positionn
of the sortedends
array. ifm == n
, then we know that the pairing is not broken forinterval[i]
. Otherwise, the pairing is broken forinterval[i]
. WLOG we supposem > n
, and we know that there arem
intervals that starts before intervali
starts, and there aren
intervals that ends before intervali
ends, and immediately we know that there arem  n
intervals that starts earlier than intervali
, but ends later than intervali
. Actually, we only need the existence of one such overdue interval. This overdue interval starts earlier than intervali
, and ends later than intervali
, which implies that it completely comprehends intervali
. This is clearly a situation that you can't attend both intervali
and this overarching interval.
Ifm < n
, then it's obvious that there be anotherm'
andn'
that belongs to one same intervali'
, and also satisfyingm' > n'
. Because if e.g. 3 intervals started before intervali
started, and 5 intervals ended before intervali
ended, then there can only be at most 3 intervals that started before intervali
and also ended before intervali
ended. The 2 intervals left must have started after intervali
have started, but also ended before intervali
ended. These 2 intervals are the intervals withm' > n
'. Intervali
contains these two intervals in this case.
End of ProofLet'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 havestarts[m] <= ends[m]
Proof: The point is, we can't havestarts[m] > ends[m
] for anym = 0..length1
.
Suppose we do havestarts[m] > ends[m]
. Then we call the interval corresponding toends[m]
the intervalk
. We prove that interval k can't exist by contradiction.
Since the arrays are sorted, them  1
intervals corresponding toends[0]..ends[m1]
must all begin beforestarts[m]
: they all ends before intervalk
, which ends atends[m]
, and we also know thatends[m] < starts[m]
, which in turn means that all thesem  1
intervals all starts beforestarts[m]
(because each interval starts before it ends). More graphically speaking, them  1
intervals corresponding toends[0]..ends[m1]
must also all corresponds tostarts[0]..starts[m1]
(although the order within may be broken).
Having this conclusion in hand, we know that there will be no way to arrangeinterval[k].start
: it has to be within the firstm  1
entries ofstarts
(because its start has to be smaller thanends[m]
, which is smaller thanstarts[m]
), which are already all taken by them  1
intervals corresponding toends[0]..ends[m1]
. Here we have the contradiction.
End of ProofLemma 3
For interval
i
, if its start is at positionm
of the sortedstarts
array, and its end is at positionn
of the sortedends
array, then this algorithm (which compares each pair of consecutive intervals) will return false.
Proof:
First, let's supposem > n
:
Ifm = n + 1
, then the proof is very easy: we would end up comparestarts[n+1]
withends[n]
, which is comparinginterval[i].start
withinterval[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;
Ifm
is arbitrarily larger thann
, 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 anyi = 1..length1
,starts[i] >= ends[i1]
.
Remind yourself thatstarts[m] = interval[i].start, ends[n] = interval[i].end
;
We apply this conclusion to the range ofi = n+1..m
:starts[n+1] >= ends[n] starts[n+2] >= ends[n+1] ... starts[m] >= ends[m1]
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[m1] <= ends[m1]
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 somem' > n'
for some intervali'
, and we apply the proof above to intervali'
).
End of ProofI 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
In your LEMMA 1:"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"

@xinyufeng16 said in Easy JAVA solution beat 98%:
@vegito2002
In your LEMMA 1:"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 wellformated. 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 interpretsm
as 1based, but when you sayn=3
, it looks like you are using 0based again. It does not really matter whether you use 0based or 1based, but you have to pick one and apply it consistently tom
andn
. 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 0based, then we havem=5, n = 3
, andmn=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.


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