Vaccination Problem

http://alokmohansharma.blogspot.com/2015/03/program-in-cc-for-vaccination-problem.html

Interview

Description:

Vaccination Problem

The world health organization wants to establish a total of B vaccination clinics across N cities to immunization people against fatal diseases. Every city must have at least 1 clinic, and a clinic can only vaccinate people in the same city where they live. The goal is to minimize the number of vaccination kits needed in the largest clinic. For example suppose you have.

1. 2 cities and
2. 7 clinics to be opened
3. 200.000 is the population of first city
4. 50,000 is the population of second city
5. Two clinics can open in the first city and
6. Five in the second. This way
7. 100,000 people can be immunized in each of the two clinics in first city, and
8. 100.000 people can be immunized in the each clinic in the second city
9. So the maximum number of people to be immunized in the largest clinic is 10,000

Input: Two integers in the first line, N, the number of cities, and B, the total number of clinics to be opened Each of the following N lines contains an integer ai, the population of city i

Output: One integer representing the maximum number of people to be immunized in any single clinic

Example:

Sample input:
2 7
200000
500000

Sample output:
100000

Idea:

use heap

Code:

#include <iostream>
#include <vector>
#include <climits>
#include <algorithm>
#include <functional>
#include <map>
#include <set>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <stack>
#include <queue>
#include <utility>
#include <memory>
#include <cmath>

using namespace std;

int vaccinationCity(int n_clinic, const vector<int> & populations){
    if(n_clinic<populations.size()) return -1;

    // auto cmp =[](int a, int b){return a<b;};
    struct CityNode{
        CityNode(int p, int nc, int l):city_population(p), num_clinic(nc), load(l){}
        int city_population;
        int num_clinic;
        int load;
    };

    struct Cmp{
        bool operator() (const CityNode & a, const CityNode &b) const {
            return a.load<b.load;
        }
    };

    priority_queue<CityNode, vector<CityNode>,  Cmp> max_heap;

    for(auto e: populations){
        max_heap.push(CityNode(e, 1, e));
    }

    for(int i=0; i<n_clinic-populations.size(); ++i){
        CityNode pq=max_heap.top();
        max_heap.pop();

        pq.num_clinic++;
        int avg_load=pq.city_population/pq.num_clinic;
        pq.load=(pq.city_population%pq.num_clinic==0) ? avg_load : avg_load+1;
        max_heap.push(pq);
    }

    return max_heap.top().load;
}




int main(){

    // int n_clinic=7;
    // vector<int> population={2000, 5000};

    int n_clinic=7;
    vector<int> populations={2, 42, 49};


    int result;

    result = vaccinationCity(n_clinic, populations);

    cout<<result<<endl;
}