Problem

Located on a line are N segments, numbered from 0 to N − 1, whose positions are given in 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:

    function solution(A, B);

that, given two 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. 

Write an efficient algorithm for the following assumptions:

·         N is an integer within the range [0..30,000];

·         each element of arrays A and 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).

Note:

The given diagram is: 

Sets of size 2 (two segments per set) that do not overlap are: {0, 2}, {0, 3}, {0, 4}, {1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 4}.

There are 8 sets of size 2 here. The number of sets do not really matter; it is the size, e.g. 2 that matters. Note that the sets {0, 1} and {3, 4} are not here because they have overlapping. 

But is the size 2 (two segments per set), the size for the maximal number of segments, where there is no overlapping? - What about the size of 3? With the size 3, the sets are: {0, 2, 3}, {0, 2, 4}, {1, 2, 3} {1, 2, 4}. There is no overlapping in any of these sets. As the size of 3 is higher than the size of 2, three is the preferred answer, since the goal is to find the size with the maximal number of segments. Note that {0, 1, 2} and {2, 3, 4} are not included here, as they have overlapping. With the size 3, there are 4 sets without overlapping, but the number of sets do not really matter, for this problem.

Well, is the size 3 (three segments per set), the size for the maximal number of segments, where there is no overlapping? - What about the size of 4? With the size 4, all the possible sets are {0, 1, 2, 3}, {1, 2, 3, 4}, {0, 2, 3, 4}, {0, 1, 3, 4}, {0, 1, 2, 4}. Each of these sets have overlapping. And so, 3 and not 4 is the answer. Even if just one of the sets for the size of 4, had no overlapping, then the size of 4 would have been returned.

Minimum Value for N

One of the assumptions given in the problem is:

·         N is an integer within the range [0..30,000]; 

So, the number of segments, N can be 0 or it can be 1. In either case, there is no possibility of overlapping or non-overlapping. And so, for each of these cases, N is returned (0 or 1 is returned). Once the number of segments go beyond 1, there is the possibility of overlapping.

Illustration

The quotation from the problem description,

“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].” means that no segment is within another segment. That is, no segment starts and ends within another segment. Seen another way, no segment overlaps another segment completely. 

The quotation from the problem description,

“The segments are sorted by their ends, which means that B[K] ≤ B[K + 1] for K such that 0 ≤ K < N − 1.” is important.

These two quotations make the solution easy, and paves the way for greedy algorithm, as a good algorithm for the solution. 

The given data is used for illustration. The diagram is:

The start of segment 1 (i=1) is less than or equal to the end of segment 0 (i=0); no set of non-overlapping segments is being formed yet. The start of segment 2 (i=2) is greater than the end of segment 0 (i=0) and is greater than the end of segment 1 (i=1). Now, the sets being formed that do not have overlapping are: {0, 2} and {1, 2}. The size so far is 2. 

The last end of interest at this point is the end of segment 0 (i=0). The start of segment 3 (i=3) is greater than the end of segment 0 (i=0), and is greater than the end of segment 1 (i=1), and is greater than the end of segment 2 (i=2). The sets being formed now without overlapping are: {0, 2, 3} and {1, 2, 3}. The size so far is 3. Note that there are two other sets of size 3, but with overlapping. These two other sets are: {0, 1, 2} and {0, 1, 3}.

The last end of interest at this point is the end of segment 2 (i=2). Segment 4 (i=4) is still to be considered. The start of segment 4 (i=4) is greater than the end of segment 0 (i=0), and is greater than the end of segment 1 (i=1), and is greater than the end of segment 2 (i=2), but it is less than or equal to the end of segment 3 (i=3). The sets being formed now from combinations of segments, without overlapping are: {0, 2, 3}, {0, 2, 4}, {1, 2, 3} and {1, 2, 4}. The size so far has remained at 3, though the number of segments have increased. Three is the maximum size for a set that has no overlapping. 3 is the answer.

Strategy

The lesson for this problem (task) is on Greedy Algorithm. That should suggest to the candidate that greedy algorithm is needed in the solution. 

If N is less than 2, return N. In this case, N is 0 or 1.

The given list is scanned beginning from 1. The value of the size is incremented by 1, whenever the beginning of a segment is encountered that is greater than the last end of interest, of a previous segment.  

Greedy Algorithm Solution

The program is (read the code and comments):

<script type='text/javascript'>
    "use strict";

function solution(A, B) {
    let N = A.length;
    if (N<2) return N;
        
    let size = 1;
    let end = B[0];    //end of first segment

    for (let i = 1; i < N; i++) {
        if (A[i] > end) { 
            size++;
            end = B[i];
        }
    }

    return size;
}

    let A = [1, 3, 7, 9, 9];
    let B = [5, 6, 8, 9, 10];
    let ret = solution(A, B);
    document.write(ret + '<br>');

 /* let C = [1, 3];
    let D = [5, 6];
    let ret1 = solution(C, D);
    document.write(ret1 + '<br>');
      */

</script>

The output is: 3. At app.codility.com/programmers the scoring and detected time complexity for this solution(), using the particular test cases at app.codility.com/programmers, is:

    Task score : 100% -  Correctness : 100% ; Performance : 100%

    Detected time complexity : O(N) 

What has the solution() function done? Consider again the given data:

    A = [1, 3, 7, 9, 9];

    B = [5, 6, 8, 9, 10]; 

Scanning begins at i=1 with an assumed set size of 1. A[1]=3 is compared with B[0]=5 and there is overlapping; the value of size remains at 1. In the next pass through the body of the for-loop, A[2]=7 is compared with B[0]=5 still, and there is no overlapping this time; the value of size is incremented from 1 to 2. The value of size, 2 without overlapping refers to the number of elements in the sets: {0, 2} and {1, 2}. Even if it was just one set, e.g. {0, 2}, the value of 2 would still have been alright here. The rest of the other sets of size 2 have not yet been formed. Those sets are {0, 3}, {0, 4}, {1, 3}, {1, 4}, {2, 3} and {2, 4}. The last end of interest at this point is the end of segment 2 (i=2), which is B[2]=8, from “end = B[2];”.

In the next pass through the body of the for-loop, A[3]=9 is compared with B[2]=8, and there is no overlapping; the value of size is incremented from 2 to 3. The value of size, 3 without overlapping refers to the sets: {0, 2, 3} and {1, 2, 3}. Other sets of 3, encountered at this stage, that have overlapping are: {0, 1, 2} and {0, 1, 3}. The last end of interest at this point is the end of segment 3 (i=3), which is B[3]=9, from “end = B[3];”. 

In the next pass through the body of the for-loop, A[4]=9 is compared with B[3]=9, and there is overlapping; the value of size remains at 3 with no increment. More non-overlapping sets have indirectly been considered. These sets are: {0, 2, 4} and {1, 2, 4}. Remember that it is not really the number of sets of 3 that matters, for this problem. Once there is at least one set of 3 elements without overlapping, that set is accepted. The for-loop ends at this point.

Suboptimal Situation

When the length of the given arrays is 2, it is assumed in the code that there is already a set whose size is 1, that does not have overlapping. That is, when the number of segments is 2, it is assumed in the code that there is already a set whose size is 1, that does not have overlapping. Well, a set of one segment, e.g {0} or {1} cannot have overlapping. That is the basis of the assumption. However, can that really happen? Can anyone talk of overlapping of segments without having two or more segments (in a set). With this assumption, all the 11 test cases at app.codility.com/programmers passed. 

What about the test case with data:

    A = [1, 3];

    B = [5, 6]; 

This just refers to the first two segments above. This data is within the commented-out symbols of the main() function above. If the comment symbols are removed, and the program executed (run) again, the output for this case would be 1, and that would be wrong, because the two segments overlapped. So, with this case, the solution() function above is subobtimal.

Thanks for reading.