Codility 'Max Nonoverlapping Segments' Solution

Martin Kysel · March 13, 2015

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

Twitter, Facebook