Merge Intervals

[darwinrlo]

Claim: Sorting by start time puts overlapping intervals right next to each other.

If two intervals A and C overlap, then if there is an interval B whose start time falls between A and C, then B overlaps with both A and C.

B is between A and C in the sorted order, so one of the following situations holds:

• B's start time could be the same as A's start time.
• B's start time could be the same as C's start time.
• B's start time falls between A and C's start time.

Claim: If there is more than one interval between A and C in the sorted order, then they all overlap with A and C and with each other.

Conclusion: If the intervals are sorted by start time, then if two intervals overlap, any interval between them in the sorted order overlap with one or both of them. These intervening intervals can be merged with one of the delimiting intervals, which in turn can be merged with each other to form a single interval.

Claims

• There are no non-overlapping intervals between two overlapping intervals. Hence, overlapping intervals are placed next to each other.
• Once a contiguous sequence of overlapping intervals has been merged, then there are no other overlapping intervals to merge with.

[darwinrlo]

If two intervals overlap, then any intervals between them overlap with both of them. They can all be merged into one interval. This is one case.

[darwinrlo]

Case: Two intervals do not overlap, but they're connected by a chain of overlapping intervals.

In the sorted order, the chain is not broken by a non-overlapping interval. In general, as we have shown previously, in the sorted order, overlapping intervals do not have intervening intervals that do not overlap with at least one of them.

The intervening intervals can be merged with one another. Then they can be merged with the original overlapping intervals, which can then be merged into one interval.

[darwinrlo]

Let a and b be the start and end of a chain of overlapping intervals. That is, a does not overlap with the interval that precedes it and b does not overlap with the interval that follows it. As we have established, this chain is contiguous in the sorted order. The whole chain can be merged into one interval.

Claim: There are no other intervals left to merge with. There are no other overlapping intervals.

This is not possible because, between two overlapping intervals in the sorted order, there are no intervening intervals that do not overlap with either of the overlapping intervals.

[darwinrlo]

Draft 2

• If two intervals overlap, there are no intervening intervals in the sorted order that do not overlap with at least one of the two intervals. The two intervals, as long as all the intervals they overlap with, can be merged into one interval.

• If two intervals do not overlap but are connected by a chain of overlapping intervals, then these intervals will be contiguous in the sorted order and can be merged into one interval. In the sorted order, as we previously established, no pair of overlapping intervals in the chain is broken by a non-overlapping interval.

• Let a and b be the first and final intervals of a contiguous sequence of overlapping intervals in the sorted order. That is, a does not overlap with the interval that precedes it and b does not overlap with the interval that follows it. This sequence can be merged into one interval and there are no other intervals to merge with because we know that overlapping intervals do not have intervening non-overlapping intervals.

(Better but still not well-written. Will need a third draft.)

[darwinrlo]

Consider two intervals a and b such that a.start <= b.start. Then a and b overlap iff b.start <= a.end.

Let a and c be two overlapping intervals such that a.start <= c.start. Let b be an interval between a and c in the sorted order. Then b.start >= a.start and b.start <= c.start.

Since a and c overlap, c.start <= a.end, which means b.start <= a.end too. Since b.start >= a.start and b.start <= a.end, b overlaps with a.

Conclusion: All intervals between a and c in the sorted order overlap with a.

[darwinrlo]

Let a[0], a[1], ..., a[n] be a maximal chain of overlapping intervals in the sorted order. Maximal means that a[0] does not overlap with the interval that precedes it and a[n] does not overlap with the interval that follows it. Merge them into a single interval A.

Claim: There are no other intervals that overlap with a[0] and no other intervals that overlap a[n]. This follows from there not being intervening intervals between two overlapping intervals, and we are given that a[0] does not overlap with the interval that precedes it and a[n] does not overlap with the interval that follows it.

[darwinrlo]

Say we have two intervals A and C with A appearing before C in the sorted order. They are not next to each other in the sorted order, which means there are intervals B[0], ..., B[n] between them. The intervals between them do not overlap with either of them. Then A and C do not overlap.

Rigorously:

• A does not overlap with B[0], which means B[0].start > A.end.
• B[n] does not overlap with C, which means B[n].end < C[start].
• B[0].start <= B[n].end, so A.end < C.start, which means A and C do not overlap.

[darwinrlo]

Say we have intervals A and C in the sorted order. They are not next to each other. In between them are intervals B[0], ..., B[n]. Somewhere between B[0] and B[n], B[i] does not overlap with B[i+1]. Then A and C do not overlap.

(We can prove this rigorously, but it would be pedantic to do so.)

[darwinrlo]

If A and C overlap, then they either overlap directly or there is an unbroken chain of overlapping intervals between them. If there were a broken chain, we can show that A and C do not overlap.

All intervals in a chain of overlapping intervals are in the same contiguous segment of the sorted order.