Order Now  +1 678 648 4277 

Algorithm Assignment solution using C++


Algorithm Assignment

The file describes a line of N students standing in a row. Each line of the file gives the name of a student and their integer height. We’ll be implementing the algorithm that sweeps downward. In particular, the main steps are:-

Read the input into a vector, where the string part is a student’s name and the int part is their height

Build a second vector, where the first part is height and the second part is their index

Sort the contents of this second vector (in order by height)

For each student in decreasing order of height

Add a student to a balanced BST keyed on an index (a set)

For each student, call the find method to get an iterate pointing to their record in the set.

Solution:

#include < iostream> #include < vector> #include < set> #include < cstdlib> using namespace std; int main() { vector> students; string data; getline(cin, data); while(!data.empty()) { students.emplace_back(data.substr(0, data.find(' ')), stoi(data.substr(data.find(' ') + 1, data.size()))); getline(cin, data); } vector> heightsByIndex; for(int i = 0; i < students.size(); i++) { heightsByIndex.emplace_back(students[i].second, i); } sort(heightsByIndex.begin(), heightsByIndex.end()); set bstOfIndex; int maxDiff = 0; int prevIndex = 0; int nextIndex = 0; for(int i = heightsByIndex.size() - 1; i >= 0; i--) { bstOfIndex.insert(heightsByIndex[i].second); set::iterator pos = bstOfIndex.find(heightsByIndex[i].second); if(pos != bstOfIndex.begin()) { int diff = abs(*pos - *prev(pos, 1)); if(maxDiff < diff) { maxDiff = diff; prevIndex = *pos; nextIndex = *prev(pos, 1); } } if(next(pos, 1) != bstOfIndex.end()) { int diff = abs(*pos - *next(pos, 1)); if(maxDiff < diff) { maxDiff = diff; prevIndex = *pos; nextIndex = *next(pos, 1); } } } cout << "Longest sight : " << maxDiff << endl << "People : " << students[prevIndex].first << " and " << students[nextIndex].first << endl; }