Memory Error
unknown
c_cpp
4 years ago
2.4 kB
17
Indexable
int MinStations(int roadLength, int range, std::vector<int> towers)
{
std::cout << "Starting the function..." << "\n";
/* implement your algorithm here */
/* you can modify or sort vector **towers** if you want */
int curr_spot = 0;
// Count of transmitters used
int count = 0;
// last transmitter position
int last_range = 0;
// Create vector to track positions covered
std::vector<int> coverage(roadLength, 0);
// Sort towers in ASC order
std::sort(towers.begin(), towers.end());
std::cout << "Starting the loop..." << "\n";
// While Loop
while (curr_spot < roadLength) {
// Get all towers that cover curr_spot
// Stack to hold towers
std::stack<int> tower_stack;
// Loop through towers
for (auto tower : towers)
{
// Find towers that cover curr_spot
if(curr_spot >= tower - range && curr_spot <= tower + range) {
std::cout << "Current tower is: " << tower << "\n";
// Push onto stack
tower_stack.push(tower);
}
}
std::cout << "For Loop finished..." << "\n";
// Should have a stack of all towers that cover curr_spot
std::cout << "Starting to pop from stack of size " << tower_stack.size() << "..." << "\n";
// If stack is empty, problem has no feasible solution
if (tower_stack.empty()) {return -1;}
// Otherwise, loop through stack
while(!tower_stack.empty()){
// Get first tower locatoin
last_range = tower_stack.top();
// Incr. count
count += 1;
std::cout << "Popping " << tower_stack.top() << "\n";
// Pop tower from stack
tower_stack.pop();
// Update Coverage
for (int i = curr_spot; i < last_range + range; i++) {
coverage[i] += 1;
}
// Check if minimum coverage is 2 -> Using GetMinElem doesn't cause seg fault
int min = INT32_MAX;
for (auto num : coverage) {
(num < min) ? min = num : min += 0;
}
if (min >= 2) {break;}
}
// Update curr_spot
// This is the furthest spot on the road with double coverage
curr_spot = last_range + range;
std::cout << "The current spot is: " << curr_spot << "\n";
std::cout << "The number of transmitters is: " << count << "\n";
}
std::cout << "\n" << "\n" << "\n";
return count; /* your answer */;
}Editor is loading...