Question Name: Max-Nonoverlapping-Segments or MaxNonoverlappingSegments
It is an easy solution, but a bit hard to prove it.
Let’s scan from left to right, according to the end points. Since the input has already been sorted with the end points, linear scan works. Firstly, we define the cluster as: let the first item of that segment be segment[i], the cluster is all the segments from segment[i] to segment[j] (both inclusive, and i <= j), such that:
for all x (i < x <= j), segment[i].begin <= segment[x].begin <= segment[i].end
Any two segments in one cluster are overlapping.
1. Because the segments are sorted as the end point, (that is, for all x (i < x <= j), segment[x].end >= segment[i].end), and the definition of cluster, all the other segments are overlapping with the first one.
2. Any two no-first segments are overlapping. Because both their begin points are <= segment[i].end, and both end points are >= segment[i].end.
End of proof. As a result, in one cluster, we can pick up AT MOST one segment.
In any two consecutive clusters, we can choose two segments MAXIMUMLY. Let cluster[i] be the i(th) cluster, and cluster[i].segment[j] be the j(th) segment in the i(th) cluster.
1. We CAN choose two. As the definition of cluster, we have:
cluster[i].segment[first].end < cluster[i+1].segment[first].begin
And with the definition of segment, we have:
cluster[i].segment[first].begin <= cluster[i].segment[first].end < cluster[i+1].segment[first].begin <= cluster[i+1].segment[first].end
Therefore, they (cluster[i].segment[first] and cluster[i+1].segment[first]) are not overlapping.
2. We can choose two AT MOST. If we can choose three or more non-overlapping segments in these two consecutive clusters, according to pigeonhole principle, at least two non-overlapping segments are in one cluster. But according to our previous discussion, it is impossible.
Similarly, we can proof that: with N clusters, we can pick up N non-overlapping segments at most. Therefore, the orginal question becomes: find the number of clusters in the segments.
def solution(A, B):
# No overlapping is possible.
if len(A) < 2: return len(A)
count = 1 # The first segment starts a new cluster.
end = B
index = 1 # The second segment.
while index < len(A):
# Skip all the segments in this cluster.
while index < len(A) and A[index] <= end: index += 1
# All segments are processed.
if index == len(A): break
# Start a new cluster.
count += 1
end = B[index]