Codility ‘Max Nonoverlapping Segments’ Solution

Posted on by
Short Problem Definition:

Find a maximal set of non((-))overlapping segments.

Link

MaxNonoverlappingSegments

Complexity:

expected worst-case time complexity is O(N)

expected worst-case space complexity is O(N)

Execution:

This can be solved by using greedy search. The beginning of the next segment must come strictly after its predecessor.

Solution:
def solution(A, B):
    if len(A) < 1:
        return 0
    
    cnt = 1
    prev_end = B[0]
    
    for idx in xrange(1, len(A)):
        if A[idx] > prev_end:
            cnt += 1
            prev_end = B[idx]
    
    return cnt

If you enjoyed this post, then make sure you subscribe to my Newsletter and/or Feed.

Facebooktwittergoogle_plusredditpinterestlinkedin
  • Jorge O

    Cool. I guess they did want a Greedy answer but how to get a correct answer in O(n) ?

    Try for example ([1,3,5,6,8], [2,4,9,7,10]) which should result in 4, your algorithm returns 3.