[Codility_16. Greedy Algorithm] MaxNonoverlappingSegments

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: def 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, 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)

서로 겹치지 않는 선분을 조합해서 최대로 만들 수 있는 선분의 개수를 구하면 된다.

A : 선분의 시작점, B : 선분의 끝점

 

상단 예제로 보았을 때, 안겹치도록 하는 방법은 5개의 선분 중 최대 3개를 사용해서 조합하는 방법 4가지({0, 2, 3}, {0, 2, 4}, {1, 2, 3}, {1, 2, 4})가 나오게 된다. 정답은 최대 몇개까지의 선분을 사용해서 안겹치게 하느냐 이므로, 최대 3개를 리턴하면 됨.

 

https://app.codility.com/demo/results/trainingPS55CM-U9U/

Test results - Codility

이 케이스의 관건은 B[0] 즉 제일 첫 선분의 끝점을 기준점으로 잡고, 그 이후의 시작점(A[i])이 기준점보다 큰 경우에 Num 개수를 하나씩 늘리면 된다. 이때, 기준점을 전체 range만큼 돌면서 비교해 나가면 된다. 

def solution(A, B):
    num = 1
    if (len(A)==0 or len(B)==0):
        return 0
    if (len(A)==1):
        return 1
    standard_endpoint = B[0]
    for i in range(1,len(A)):
        if(standard_endpoint<A[i]):
            num+=1
            standard_endpoint=B[i]
    return num