Solution to Max-Nonoverlapping-Segments by Codility

4 Sep

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.

9 Replies to “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

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

  4. It seems there is some anomaly in the problem statement of Codility. The statement “Two segments I and J, such that I β‰  J, are overlapping if they share at least one common point.” That means even single point segment overlaps. Now check the segments 3 and 4. They overlap on point 9. It means segment 0 and segment 1 overlap as well as segment 3 and 4 overlap. Only segment 2 is non-overlapping. Then read this statement “The size of a non-overlapping set containing a maximal number of segments is 3.”, which according to me is wrong. It is only one and not three.
    Or else can you explain it?

    • You might misunderstand the question.
      β€œThe size of a non-overlapping set containing a maximal number of segments is 3.”: you missed the keyword set.
      As you said: “It means segment 0 and segment 1 overlap as well as segment 3 and 4 overlap. Only segment 2 is non-overlapping.”. So we can have a set of segments {0, 2, 4}, in which no element overlaps with any other. And 3 is the number of the segments in the set.

  5. This is greedy. Simple solution but bit hard understand.

    • For those who couldn’t understand, let’s see if I can help:

      This algorithm has basically one job: from our first ever segment(that starts in A[0] and ends at B[0]), find whatever segment starts after our first segment ended(in other words where A[i] > B[0]). If we find one, increase a counter, and we then start treating that segment as we treated our first one: if in the loop we find another segment that starts after the segment we just found ends, we increase the counter again, and so on and so forth. That’s the job of the variable “ni”, to hold the index where the last segment we found ended, to compare with the next ones.

      One factor that makes this solution suboptimal(but is what codility wants) is that we always have at least one non overlapping segment, even though we can have situations where we have 0 non overlapping segments(like A[1,1,1] and B[1,1,1]). But codility is ok with that because there it is a test that tests that exactly scenario(the test is called “small_all_overlapping”), and when our algorithm here returns 1 codility evaluates as correct.

Leave a Reply to Sheng Cancel reply

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

Please put your code into a <pre>YOUR CODE</pre> section. Thanks and Happy Coding!