Memory Error
unknown
c_cpp
3 years ago
2.4 kB
12
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...