Lesson 14: MaxNonoverlappingSegments (Max Non-overlapping Segments)

Lesson 14: MaxNonoverlappingSegments (Max Non-overlapping Segments)
https://codility.com/programmers/lessons/15

As the segments are sorted in ascending order by their ends, we can use a greedy algorithm. First, we take the segment at the head, count it. Then we skip until the next non overlapping segment. 

This gives the 100% score.

int solution(int A[], int B[], int N) 
{
    //if N <= 1, we know the answer already.
    if (N <= 1){
        return N;
    }
    
    int cnt = 1;
    int prev_end = B[0];
    
    int curr;
    for (curr = 1; curr < N; curr++){
        if (A[curr] > prev_end){
            cnt++;
            prev_end = B[curr];
        }
    }
    
    return cnt;
}