Question: https://codility.com/demo/take-sample-test/max_nonoverlapping_segments/

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.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
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[0] 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] return count |

It appears you didn’t use the extra O(N) space at all because you discover the alternative is to find out the “cluster”.

As a dummy developer, I always ignore the details. ðŸ™‚ Yes, I used the extra space. But, again, details… I didn’t figure out that there is always one nonoverlapped segment as long as the array is not empty… So, whenever Codility expects returning 1, I returned 0…

The extra space is taken to store the smallest B[i] in a “cluster” (well, if I borrow your concept of cluster). We greedily stop this propagation if two nonoverlapping segments are just found.

My solution

I removed your solution. Please verify its correctness before posting. Thanks!

Every segment end is an opportunity for a non overlapping segment but only if the start of that segment did not begin before the end of the previous non overlapping segment. Since the segments are already sorted by their end then a simple traverse should suffice.

In python

Your concept is hard to understand until I figure out that we only need to use greedy to solve this.

and the fact that we have to ignore overlapping segments in current set.