Lesson 14. Binary search algorithm - NailingPlanks #1

1. 문제

You are given two non-empty arrays A and B consisting of N integers. These arrays represent N planks.
More precisely, A[K] is the start and B[K] the end of the K−th plank.

Next, you are given a non-empty array C consisting of M integers. This array represents M nails. More precisely, C[I] is the position where you can hammer in the I−th nail.

We say that a plank (A[K], B[K]) is nailed if there exists a nail C[I] such that A[K] ≤ C[I] ≤ B[K].

The goal is to find the minimum number of nails that must be used until all the planks are nailed. In other words, you should find a value J such that all planks will be nailed after using only the first J nails. More precisely, for every plank (A[K], B[K]) such that 0 ≤ K < N, there should exist a nail C[I] such that I < J and A[K] ≤ C[I] ≤ B[K].

For example, given arrays A, B such that:
A[0] = 1    B[0] = 4
A[1] = 4    B[1] = 5
A[2] = 5    B[2] = 9
A[3] = 8    B[3] = 10
four planks are represented: [1, 4], [4, 5], [5, 9] and [8, 10].

Given array C such that:
C[0] = 4
C[1] = 6
C[2] = 7
C[3] = 10
C[4] = 2
if we use the following nails:
  - 0, then planks [1, 4] and [4, 5] will both be nailed.
  - 0, 1, then planks [1, 4], [4, 5] and [5, 9] will be nailed.
  - 0, 1, 2, then planks [1, 4], [4, 5] and [5, 9] will be nailed.
  - 0, 1, 2, 3, then all the planks will be nailed.

Thus, four is the minimum number of nails that, used sequentially, allow all the planks to be nailed.

Write a function:
  int solution(vector<int> &A, vector<int> &B, vector<int> &C);

that, given two non-empty arrays A and B consisting of N integers and a non-empty array C consisting of M integers, returns the minimum number of nails that, used sequentially, allow all the planks to be nailed.
If it is not possible to nail all the planks, the function should return −1.

For example, given arrays A, B, C such that:
A[0] = 1    B[0] = 4
A[1] = 4    B[1] = 5
A[2] = 5    B[2] = 9
A[3] = 8    B[3] = 10

C[0] = 4
C[1] = 6
C[2] = 7
C[3] = 10
C[4] = 2

the function should return 4, as explained above.

Write an efficient algorithm for the following assumptions:
  - N and M are integers within the range [1..30,000];
  - each element of arrays A, B and C is an integer within the range [1..2*M];
  - A[K] ≤ B[K].

 

주어진 못으로, 못질을 할 때, 언제 모든 판자에 못을 박을 수 있는지 구하는 문제. (못을 순서대로 써야 한다)

 

예시) return 4

	[0]	[1]	[2]	[3]	[4]
A (판자 시직 위치)	1	4	5	8
B (판자 종료 위치)	4	5	9	10
C (못 위치)	4	6	7	10	2

 

판자 = [1, 4] / [4, 5] / [5, 9] / [8, 10]

 

첫번째, C[0]  못을 박는다.

판자 [1, 4] 와 [4, 5]에 못이 박힌다. 

 

두번째, C[1] 못을 박는다

판자 [5, 9]에 못이 박힌다.

 

세번째, C[2] 못을 박는다.

판자 [5, 9]에 못이 박히지만, 이미 C[1]에 의해서 못이 박혀 있다.

 

네번째, C[3] 못을 박는다.

판자 [8, 10] 에 못이 박힌다. 이로써 모든 판자에 못이 박혔다. (사용한 못 4개, return 4)

 

2. 매개변수 조건

• vector A, B 크기(N): 1 ~ 30,000
• vector C 크기(M) : 1 ~ 30,000
• vector A, B, C 요소 값 범위: 1 ~ M * 2

 

3. 코드 (C++)

판자들을 map으로 정리했다.

판자가 같은 위치에서 시작할 수 있으므로, multimap을 사용했다.

 

map으로 판자들을 정리한 이유는,

판자의 위치가 정렬되어 있으면, 현재 못(C[i])이 모든 판자에 박을 수 있는지 확인할 필요가 없기 때문이다.

#include <map>

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

    multimap<int, int> planks = {};
    for(size_t i = 0; i < A.size(); i++)
    {
        planks.insert({A[i], B[i]});
    }

    int i = 0;
    for(i = 0; i < (int)C.size(); i++)
    {
        auto it = planks.begin();
        while(it != planks.end())
        {
            if(C[i] < it->first) break; //현재의 못으로는 더 못질할 수 없다

            if(it->first <= C[i] && C[i] <= it->second)
            {
                it = planks.erase(it); //못질이 되면 삭제한다
                if(planks.empty()) break;
            }
            else
            {
                it++;
            }
        }

        if(planks.empty()) break;
    }

    if(planks.empty()) return i + 1;
    return -1;
}

 

 

4. 결과