circus - tower

/* From Cracking the Coding Interview 9-7 */

/* A circus is designing a tower routine consisting of people standing atop one another’s shoulders.

 For practical and aesthetic reasons, each person must be both shorter and lighter than the person below him or her. Given the heights and weights of each person in the circus,

 write a method to compute the largest possible number of people in such a tower. */

struct person{

    person(){};

    person(int, int);

    bool operator<(person &);

    int ht, wt;

};

person::person(int ht, int wt) {

    this->ht = ht; this->wt = wt;

}

bool person::operator<(person & p) {

    return (this->ht < p.ht && this->wt < p.wt);

}

class circus {

public:

    circus(int *, int);

    int getHighestTower();

private:

    void getTower(bool *, vector<int>, int, int &);

private:

    int numPeople;

    vector<person> member;

    vector<int> tower;

};

circus::circus(int * arr, int n): numPeople(n/2) {

    for (int i = 0; i < numPeople; ++i) {

        person p;

        p.ht = arr[2*i];

        p.wt = arr[2*i+1];

        member.push_back(p);

    }

}

int circus::getHighestTower() {

    int maxNumber = 1;

    vector<int> v;

    bool * b = new bool[numPeople];

    for (int i = 0; i < numPeople; ++i) {

        b[i] = true; v.push_back(i);

        getTower(b, v, i, maxNumber);

        b[i] = false; v.pop_back();

    }

    delete [] b;

    return maxNumber;

}

void circus::getTower(bool * b, vector<int> v, int current, int & maxNumber) {

    if (v.size() > maxNumber) {

        maxNumber = (int) v.size();

        tower = v;

    }

    for (int i = 0; i < numPeople; ++i) {

        if (!b[i] && member[current] < member[i]) {

            b[i] = true; v.push_back(i);

            getTower(b, v, i, maxNumber);

            b[i] = false; v.pop_back();

        }

    }

}