Memory Error

mail@pastecode.io avatar
unknown
c_cpp
2 years ago
2.4 kB
10
Indexable
Never
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 */;
}