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.

  • Trupti Kulkarni

    Using Java got 100% correctness and 20% Performance.. Please guide to improve the performace

    class Solution {
    public int solution(int[] A, int[] B) {
    // write your code in Java SE 8
    int count,maxcount=0;
    if(A.length==0)
    return 0;
    else
    {

    for(int j=0;j<B.length;j++)
    {
    count=1;
    int prev_end=B[j];
    for(int i=1;iprev_end)
    {
    count++;
    // System.out.println(prev_end);
    prev_end=B[i];

    }
    }
    maxcount = maxcount<count?count:maxcount;
    }
    }
    return maxcount;
    }
    }

    • hi Trupti,

      thanks for sharing your code. The formatting is mangled beyond my ability to understand the code. Seems like some HTML is mixed into it.