# Codility ‘Max Nonoverlapping Segments’ Solution

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

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