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] = 10four 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] = 2if 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] = 2the 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].
#include <algorithm>
// Let's define a convenient structure to hold both index position and
// the index of the nail in original nails lists
struct Nail {
int nail_pos;
int nail_index;
};
// an auxiliary function to help us in sorting nails
int compare(Nail &a, Nail &b);
// finding the earliest nail to fix the plank. The implementation can be found after the solution function
int find_first_nail(int plank_begin, int plank_end, std::vector<Nail> &nails, int previous_plank_nail_index);
int solution(const std::vector<int> &A, const std::vector<int> &B, const std::vector<int> &C) {
const int M = C.size();
// let's fill our ordered nail list
std::vector<Nail> nails;
nails.reserve(M);
for (int i = 0; i < M; ++i) {
Nail nail;
nail.nail_index = i;
nail.nail_pos = C[i];
nails.push_back(nail);
}
// Usually, the C++ implementations of sort takes O(M log M)
std::sort(nails.begin(), nails.end(), compare);
int target_nail_index = -1;
const int N = A.size();
int previous_plank_nail_index = -1;
// O(N log M)
for (int i = 0; i < N; ++i) {
// using binary search to find the earliest nail given a plank.
int nail_index = find_first_nail(A[i], B[i], nails, previous_plank_nail_index);
if (nail_index == -1) {
return -1;
}
// only update target_nail_index if the new nail index is after it
if (nail_index > target_nail_index) {
target_nail_index = nail_index;
previous_plank_nail_index = target_nail_index;
}
}
// The resulting time complexity O(N log M + M log M) = O((N + M) log M)
return target_nail_index + 1;
}
int find_first_nail(int plank_begin, int plank_end, std::vector<Nail> &nails, int previous_plank_nail_index) {
int lower = 0;
int upper = nails.size() - 1;
int lowest_nail_index = -1;
// first, we perform binary search to find the lowest nail position
while (lower <= upper) {
int mid = (lower + upper) / 2;
Nail &nail = nails[mid];
if (nail.nail_pos > plank_end) {
upper = mid - 1;
} else if (nail.nail_pos < plank_begin) {
lower = mid + 1;
} else {
// keeping looking for a suitable nail before mid
upper = mid - 1;
lowest_nail_index = mid;
}
}
int result = -1;
if (lowest_nail_index > -1) {
// okay. We found the index of the lowest nail inside the plank limits
// but now, we must to find the earlier nail inside the plank limits
// this is done using linear search over the ordered nails starting from lowest_nail_index + 1
// the search finishes when:
// - we find a nail after plank end or
// - we reach the end of nails list
// - we find a nail index which is before the previous plank nail
result = nails[lowest_nail_index].nail_index;
for (int i = lowest_nail_index + 1; result > previous_plank_nail_index && i < nails.size(); i++) {
auto & nail = nails[i];
int nail_pos = nail.nail_pos;
if (nail_pos > plank_end) {
break;
} else if (nail.nail_index < result) {
result = nail.nail_index;
}
}
}
return result;
}
int compare(Nail &a, Nail &b) {
if (a.nail_pos < b.nail_pos)
return true;
else if (a.nail_pos > b.nail_pos)
return false;
else if (a.nail_index < b.nail_index)
return true;
else if (a.nail_index > b.nail_index)
return false;
else return true;
}
#include <algorithm>
// Let's define a convenient structure to hold both index position and
// the index of the nail in original nails lists
struct Nail {
int nail_pos;
int nail_index;
};
// an auxiliary function to help us in sorting nails
int compare(Nail &a, Nail &b);
// finding the earliest nail to fix the plank. The implementation can be found after the solution function
int find_first_nail(int plank_begin, int plank_end, std::vector<Nail> &nails, int previous_plank_nail_index);
int solution(std::vector<int> &A, std::vector<int> &B, std::vector<int> &C) {
const int M = C.size();
// let's fill our ordered nail list
std::vector<Nail> nails;
nails.reserve(M);
for (int i = 0; i < M; ++i) {
Nail nail;
nail.nail_index = i;
nail.nail_pos = C[i];
nails.push_back(nail);
}
// Usually, the C++ implementations of sort takes O(M log M)
std::sort(nails.begin(), nails.end(), compare);
int target_nail_index = -1;
const int N = A.size();
int previous_plank_nail_index = -1;
// O(N log M)
for (int i = 0; i < N; ++i) {
// using binary search to find the earliest nail given a plank.
int nail_index = find_first_nail(A[i], B[i], nails, previous_plank_nail_index);
if (nail_index == -1) {
return -1;
}
// only update target_nail_index if the new nail index is after it
if (nail_index > target_nail_index) {
target_nail_index = nail_index;
previous_plank_nail_index = target_nail_index;
}
}
// The resulting time complexity O(N log M + M log M) = O((N + M) log M)
return target_nail_index + 1;
}
int find_first_nail(int plank_begin, int plank_end, std::vector<Nail> &nails, int previous_plank_nail_index) {
int lower = 0;
int upper = nails.size() - 1;
int lowest_nail_index = -1;
// first, we perform binary search to find the lowest nail position
while (lower <= upper) {
int mid = (lower + upper) / 2;
Nail &nail = nails[mid];
if (nail.nail_pos > plank_end) {
upper = mid - 1;
} else if (nail.nail_pos < plank_begin) {
lower = mid + 1;
} else {
// keeping looking for a suitable nail before mid
upper = mid - 1;
lowest_nail_index = mid;
}
}
int result = -1;
if (lowest_nail_index > -1) {
// okay. We found the index of the lowest nail inside the plank limits
// but now, we must to find the earlier nail inside the plank limits
// this is done using linear search over the ordered nails starting from lowest_nail_index + 1
// the search finishes when:
// - we find a nail after plank end or
// - we reach the end of nails list
// - we find a nail index which is before the previous plank nail
result = nails[lowest_nail_index].nail_index;
for (int i = lowest_nail_index + 1; result > previous_plank_nail_index && i < nails.size(); i++) {
auto & nail = nails[i];
int nail_pos = nail.nail_pos;
if (nail_pos > plank_end) {
break;
} else if (nail.nail_index < result) {
result = nail.nail_index;
}
}
}
return result;
}
int compare(Nail &a, Nail &b) {
if (a.nail_pos < b.nail_pos)
return true;
else if (a.nail_pos > b.nail_pos)
return false;
else if (a.nail_index < b.nail_index)
return true;
else if (a.nail_index > b.nail_index)
return false;
else return true;
}
#include <algorithm>
// Let's define a convenient structure to hold both index position and
// the index of the nail in original nails lists
struct Nail {
int nail_pos;
int nail_index;
};
// an auxiliary function to help us in sorting nails
int compare(Nail &a, Nail &b);
// finding the earliest nail to fix the plank. The implementation can be found after the solution function
int find_first_nail(int plank_begin, int plank_end, std::vector<Nail> &nails, int previous_plank_nail_index);
int solution(std::vector<int> &A, std::vector<int> &B, std::vector<int> &C) {
const int M = C.size();
// let's fill our ordered nail list
std::vector<Nail> nails;
nails.reserve(M);
for (int i = 0; i < M; ++i) {
Nail nail;
nail.nail_index = i;
nail.nail_pos = C[i];
nails.push_back(nail);
}
// Usually, the C++ implementations of sort takes O(M log M)
std::sort(nails.begin(), nails.end(), compare);
int target_nail_index = -1;
const int N = A.size();
int previous_plank_nail_index = -1;
// O(N log M)
for (int i = 0; i < N; ++i) {
// using binary search to find the earliest nail given a plank.
int nail_index = find_first_nail(A[i], B[i], nails, previous_plank_nail_index);
if (nail_index == -1) {
return -1;
}
// only update target_nail_index if the new nail index is after it
if (nail_index > target_nail_index) {
target_nail_index = nail_index;
previous_plank_nail_index = target_nail_index;
}
}
// The resulting time complexity O(N log M + M log M) = O((N + M) log M)
return target_nail_index + 1;
}
int find_first_nail(int plank_begin, int plank_end, std::vector<Nail> &nails, int previous_plank_nail_index) {
int lower = 0;
int upper = nails.size() - 1;
int lowest_nail_index = -1;
// first, we perform binary search to find the lowest nail position
while (lower <= upper) {
int mid = (lower + upper) / 2;
Nail &nail = nails[mid];
if (nail.nail_pos > plank_end) {
upper = mid - 1;
} else if (nail.nail_pos < plank_begin) {
lower = mid + 1;
} else {
// keeping looking for a suitable nail before mid
upper = mid - 1;
lowest_nail_index = mid;
}
}
int result = -1;
if (lowest_nail_index > -1) {
// okay. We found the index of the lowest nail inside the plank limits
// but now, we must to find the earlier nail inside the plank limits
// this is done using linear search over the ordered nails starting from lowest_nail_index + 1
// the search finishes when:
// - we find a nail after plank end or
// - we reach the end of nails list
// - we find a nail index which is before the previous plank nail
result = nails[lowest_nail_index].nail_index;
for (int i = lowest_nail_index + 1; result > previous_plank_nail_index && i < nails.size(); i++) {
auto & nail = nails[i];
int nail_pos = nail.nail_pos;
if (nail_pos > plank_end) {
break;
} else if (nail.nail_index < result) {
result = nail.nail_index;
}
}
}
return result;
}
int compare(Nail &a, Nail &b) {
if (a.nail_pos < b.nail_pos)
return true;
else if (a.nail_pos > b.nail_pos)
return false;
else if (a.nail_index < b.nail_index)
return true;
else if (a.nail_index > b.nail_index)
return false;
else return true;
}
#include <algorithm>
// Let's define a convenient structure to hold both index position and
// the index of the nail in original nails lists
struct Nail {
int nail_pos;
int nail_index;
};
// an auxiliary function to help us in sorting nails
int compare(Nail &a, Nail &b);
// finding the earliest nail to fix the plank. The implementation can be found after the solution function
int find_first_nail(int plank_begin, int plank_end, std::vector<Nail> &nails, int previous_plank_nail_index);
int solution(std::vector<int> &A, std::vector<int> &B, std::vector<int> &C) {
const int M = C.size();
// let's fill our ordered nail list
std::vector<Nail> nails;
nails.reserve(M);
for (int i = 0; i < M; ++i) {
Nail nail;
nail.nail_index = i;
nail.nail_pos = C[i];
nails.push_back(nail);
}
// Usually, the C++ implementations of sort takes O(M log M)
std::sort(nails.begin(), nails.end(), compare);
int target_nail_index = -1;
const int N = A.size();
int previous_plank_nail_index = -1;
// O(N log M)
for (int i = 0; i < N; ++i) {
// using binary search to find the earliest nail given a plank.
int nail_index = find_first_nail(A[i], B[i], nails, previous_plank_nail_index);
if (nail_index == -1) {
return -1;
}
// only update target_nail_index if the new nail index is after it
if (nail_index > target_nail_index) {
target_nail_index = nail_index;
previous_plank_nail_index = target_nail_index;
}
}
// The resulting time complexity O(N log M + M log M) = O((N + M) log M)
return target_nail_index + 1;
}
int find_first_nail(int plank_begin, int plank_end, std::vector<Nail> &nails, int previous_plank_nail_index) {
int lower = 0;
int upper = nails.size() - 1;
int lowest_nail_index = -1;
// first, we perform binary search to find the lowest nail position
while (lower <= upper) {
int mid = (lower + upper) / 2;
Nail &nail = nails[mid];
if (nail.nail_pos > plank_end) {
upper = mid - 1;
} else if (nail.nail_pos < plank_begin) {
lower = mid + 1;
} else {
// keeping looking for a suitable nail before mid
upper = mid - 1;
lowest_nail_index = mid;
}
}
int result = -1;
if (lowest_nail_index > -1) {
// okay. We found the index of the lowest nail inside the plank limits
// but now, we must to find the earlier nail inside the plank limits
// this is done using linear search over the ordered nails starting from lowest_nail_index + 1
// the search finishes when:
// - we find a nail after plank end or
// - we reach the end of nails list
// - we find a nail index which is before the previous plank nail
result = nails[lowest_nail_index].nail_index;
for (int i = lowest_nail_index + 1; result > previous_plank_nail_index && i < nails.size(); i++) {
auto & nail = nails[i];
int nail_pos = nail.nail_pos;
if (nail_pos > plank_end) {
break;
} else if (nail.nail_index < result) {
result = nail.nail_index;
}
}
}
return result;
}
int compare(Nail &a, Nail &b) {
if (a.nail_pos < b.nail_pos)
return true;
else if (a.nail_pos > b.nail_pos)
return false;
else if (a.nail_index < b.nail_index)
return true;
else if (a.nail_index > b.nail_index)
return false;
else return true;
}
The solution obtained perfect score.