Lesson 14: Max Non-overlapping Segments

https://github.com/acprimer/Codility/blob/master/src/Lesson14/MaxNonoverlappingSegments.java

https://codility.com/programmers/lessons/15

Located on a line are N segments, numbered from 0 to N − 1, whose positions are given in zero-indexed arrays A and B. For each I (0 ≤ I < N) the position of segment I is from A[I] to B[I] (inclusive). The segments are sorted by their ends, which means that B[K] ≤ B[K + 1] for K such that 0 ≤ K < N − 1.

Two segments I and J, such that I ≠ J, are overlapping if they share at least one common point. In other words, A[I] ≤ A[J] ≤ B[I] or A[J] ≤ A[I] ≤ B[J].

We say that the set of segments is non-overlapping if it contains no two overlapping segments. The goal is to find the size of a non-overlapping set containing the maximal number of segments.

For example, consider arrays A, B such that:

    A[0] = 1    B[0] = 5
    A[1] = 3    B[1] = 6
    A[2] = 7    B[2] = 8
    A[3] = 9    B[3] = 9
    A[4] = 9    B[4] = 10

The segments are shown in the figure below.

The size of a non-overlapping set containing a maximal number of segments is 3. For example, possible sets are {0, 2, 3}, {0, 2, 4}, {1, 2, 3} or {1, 2, 4}. There is no non-overlapping set with four segments.

Write a function:

int solution(int A[], int B[], int N);

that, given two zero-indexed arrays A and B consisting of N integers, returns the size of a non-overlapping set containing a maximal number of segments.

For example, given arrays A, B shown above, the function should return 3, as explained above.

Assume that:

• N is an integer within the range [0..30,000];
• each element of arrays A, B is an integer within the range [0..1,000,000,000];
• A[I] ≤ B[I], for each I (0 ≤ I < N);
• B[K] ≤ B[K + 1], for each K (0 ≤ K < N − 1).

Complexity:

• expected worst-case time complexity is O(N);
• expected worst-case space complexity is O(N), beyond input storage (not counting the storage required for input arguments).

Elements of input arrays can be modified.

Then we skip until the next non overlapping segment. 

http://blog.csdn.net/caopengcs/article/details/41841625
给定N条线段，每条线段是[A[i],B[i]]的形式（闭区间），线段已经按照结束端点排序了，求最多能选出多少条没有公共点的线段。

数据范围 N [0..30000], A, B数组都是整数，范围[0..10^9]。

要求复杂度： 时间空间都是O(1)。

分析： 这个就是活动安排问题……而且区间都按右端点排序了，贪心一个一个取，相交就扔掉就可以了。

1. int solution(vector<int> &A, vector<int> &B) {  
2.     int last = -1, answer = 0;  
3.     for (int i = 0; i < A.size(); ++i) {  
4.         if ((last < 0) || (A[i] > B[last])) {  
5.             last = i;  
6.             ++answer;  
7.         }  
8.     }  
9.     return answer;  
10. } 

    public int solution(int[] A, int[] B) {
        int ans = 0, pre = -1;
        for (int i = 0; i < A.length; i++) {
            if (A[i] > pre) {
                ans++;
                pre = B[i];
            }
        }
        return ans;
    }
https://codility.com/programmers/lessons/15