Lesson 14: MaxNonoverlappingSegments

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

セグメントの右端でソートされているため、greedy algorithmで先頭から取って行けばOKです。　まず最初のセグメントをとって１とし、その次のオーバラッピングしてないセグメントを見つけたらそれをカウントします。それを繰り返します。

これで１００％のスコアになります。

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;
}