Lesson 16. Gready algorithm - MaxNonoverlappingSegments

1. 문제

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:
  int solution(vector<int> &A, vector<int> &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).

 

겹치지 않는 선분들의 최대 집합(갯수)을 찾는 문제.

주어진 선분들은 끝나는 점(Vector B)을 기준으로 정렬(오름차순) 되어있다. ( B[K] <= B[K + 1] )

 

예시) return 3

index	A	B
0	1	5
1	3	6
2	7	8
3	9	9
4	9	10

 

그림으로 그리면 다음과 같다. 

 

(A[0], B[0])은 (A[1], B[1])과 겹친다.

(A[3], B[3])은 (A[4], B[4])와 겹친다.

 

따라서 다음과 같이 총 4개의 경의 수가 만들어지고,

{선분0, 선분2, 선분3},

{선분0, 선분2, 선분4}, 

{선분1, 선분2, 선분3},

{선분1, 선분2, 선분4}

 

모두 3개의 선분이 선택되므로, 선택할 수 있는 최대 선분 개수는 3이 된다.

 

2. 매개변수 조건

• Vector A, B 크기: 0 ~ 30,000
• Vector A, B요소 값: 0 ~ 1,000,000,000
• $A[K]<=B[K]$
• $B[K]<=B[K+1]$

 

3. 문제풀이 전략

그리디 알고리즘, 그리디 알고리즘이란? 매 순간 당장 최적인 답을 선택하는 알고리즘.

주의할점은 매 순간 최적이, 종합적으로도 최적이라는 보장은 없다. 따라서 그리디 알고리즘은 항상 최적의 해를 도출하지는 못한다.

 

이 문제에서 그리디 알고리즘은 가장 일찍 끝나는 점(B)을 선택하는 것이다.

왜냐하면, 가장 일찍 끝나는 점(B)을 선택했을 때, 뒤에 오는 선분들과 겹치지 않을 가능성이 커지기 때문이다.

 

선분들은 끝나는 점(B)으로 정렬되어 있으므로, 

첫번째 선분을 시작으로, 겹치지 않는 선문들을 선택하면 된다.

따라서 그리디 알고리즘으로 예시를 풀어보면, (0, 2, 3)을 선택할 것이다.

 

3. 코드 (C++)

int solution(vector<int> &A, vector<int> &B) {

    if(A.empty() || B.empty()) return 0;

    int cnt = 1;
    int b = B[0];    
    for(size_t i = 1; i < A.size(); i++)
    {
        if(b < A[i])
        {
            cnt++;
            b = B[i];
        }
    }

    return cnt;

 

4. 결과