5278: NailingPlanks
[Creator : ]
Description
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].
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 A[1] = 4 A[2] = 5 A[3] = 8
B[0] = 4 B[1] = 5 B[2] = 9 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.
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].
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 A[1] = 4 A[2] = 5 A[3] = 8
B[0] = 4 B[1] = 5 B[2] = 9 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.
Input
Input is given from Standard Input in the following format:
N
A1 ... AN
B1 ... BN
M
C1 ... CM
N
A1 ... AN
B1 ... BN
M
C1 ... CM
Output
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.
If it is not possible to nail all the planks, the function should return −1.
Sample 1 Input
4
1 4 5 8
4 5 9 10
5
4 6 7 10 2
Sample 1 Output
4