Codility ‘Max Nonoverlapping Segments’ Solution

Short Problem Definition:

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




expected worst-case time complexity is O(N)

expected worst-case space complexity is O(N)


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

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.

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