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