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