Solution to Max-Nonoverlapping-Segments by Codility

4 Sep


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.

4 thoughts on “Solution to Max-Nonoverlapping-Segments by Codility

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

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

Leave a Reply

Your email address will not be published. Required fields are marked *