StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>The "hospitals/residents problem" could indeed work but it depends of your constraints :</p> <ul> <li>Hospital have a maximum capacity and will order the resident (most wanted to less wanted).</li> <li>Residents will order hospitals.</li> <li>No other constraints possible.</li> </ul> <p>In your case the hospitals are workers and the residents are slots.</p> <ul> <li>Slots can order workers (maybe you prefer experimented ones in the morning...).</li> <li>Workers can order slots.</li> <li>But you can't have other constraints such as : "I've worked in the morning, I don't want to work the same day in the evening".</li> </ul> <p>If that's ok for you then you have to possibilities :</p> <ul> <li><p>you want to advantage workers : "hospital oriented case".</p> <p>You will try to assign workers to their preferred slot(s).</p></li> <li><p>you want to advantage slots : "resident oriented case"</p> <p>Each slot will have their preferred workers.</p></li> </ul> <p>I had to code it last year, here is the code.</p> <pre><code>/* RO : needed for Resident-Oriented version HO : needed for Hospital-Oriented version */ const int MAX_R = 1000; const int MAX_H = 1000; const int INF = 1000*1000*1000; </code></pre> <p>You need to fill the input variables. Everything is straightforward :</p> <ul> <li>R_pref and H_pref are the list of preferences for residents/hospitals</li> <li>H_rank[h][r] is the rank of r in H_pref[h] : the position of r in the preference list of h</li> </ul> <p>That's all.</p> <pre><code>// Input data int R, H; // Number of Residents/Hospitals int C[MAX_H]; // Capacity of hospitals vector<int> R_pref[MAX_R], H_pref[MAX_H]; // Preferences : adjency lists /*RO*/int H_rank[MAX_H][MAX_R]; // Rank : rank of r in H_pref[h] /*HO*/int R_rank[MAX_R][MAX_H]; // Rank : rank of h in R_pref[r] </code></pre> <p>No need to touch below.</p> <pre><code>// Internal data int RankWorst[MAX_H]; // Rank of the worst r taken by h /*RO*/int BestH[MAX_R]; // Indice of the best h in R_pref the r can get /*HO*/int BestR[MAX_H]; // Indice of the best r in H_pref the h can get int Size[MAX_H]; // Number of residents taken by h // Output data int M[MAX_R]; void stable_hospitals_RO() { for(int h = 0 ; h < H ; h++) RankWorst[h] = H_pref[h].size()-1; fill_n(BestH, R, 0); fill_n(Size, H,0); fill_n(M,R,INF); for (int i = 0; i < R; i++) for (int r = i; r >= 0;) { if(BestH[r] == int(R_pref[r].size())) break; const int h = R_pref[r][BestH[r]++]; if(Size[h]++ < C[h]) { M[r] = h; break; } int WorstR = H_pref[h][RankWorst[h]]; while(WorstR == INF || M[WorstR] != h) // Compute the worst WorstR = H_pref[h][--RankWorst[h]]; if(H_rank[h][r] < RankWorst[h]) // Ranked better that worst { M[r] = h; M[r = WorstR] = INF; // We have eliminate it, he need to put it somewhere } } } void stable_hospitals_HO() { fill_n(BestR, H, 0); fill_n(Size, H,0); fill_n(M,R,INF); vector<int> SH; for (int h = 0; h < H; h++) SH.push_back(h); while(!SH.empty()) { int h = SH.back(); if(Size[h] == C[h] || BestR[h] == int(H_pref[h].size())) // Full or no r available { SH.pop_back(); break; } const int r = H_pref[h][BestR[h]++]; // r is unassigned or prefer h to current hospital if(M[r] == INF || R_rank[r][h] < R_rank[r][M[r]]) { if(++Size[h] == C[h]) // Will be full SH.pop_back(); if(M[r] != INF) // Delete from M[r] { Size[M[r]]--; SH.push_back(M[r]); } M[r] = h; } } } </code></pre> <p>Example of use to show how to build rank from prefs. (In that case the preference lists were on the stdin).</p> <pre><code>int main() { scanf("%d%d",&R,&H); int num; // put inf for(int r = 0 ; r < R ; r++) { scanf("%d",&num); R_pref[r].resize(num); for(int h = 0 ; h < num ; h++) { scanf("%d",&R_pref[r][h]); R_rank[r][R_pref[r][h]] = h; } } for(int h = 0 ; h < H ; h++) { scanf("%d",&C[h]); scanf("%d",&num); H_pref[h].resize(num); for(int r = 0 ; r < num ; r++) { scanf("%d",&H_pref[h][r]); H_rank[h][H_pref[h][r]] = r; } } stable_hospitals_RO(); printf("\n\n\n\n"); stable_hospitals_HO(); return 0; } </code></pre> <p>On an example : Hospitals 1 to 3, 6 résidents.</p> <p>H_pref : </p> <ul> <li>1 -> 2 5 6 1 (prefers 2 then 5 then 6 then 1)</li> <li>2 -> 4 2 1 6 3 5</li> <li>3 -> 1 2</li> </ul> <p>R_pref : </p> <ul> <li>1 -> 1 2 3</li> <li>2 -> 3 1</li> <li>3 -> 2 1</li> <li>4 -> 1 3 2</li> <li>5 -> 3 2 1</li> <li>6 -> 3</li> </ul> <p>H_rank : </p> <ul> <li>1 -> 4 1 INF INF 2 3 (1 is in position 4 in H_pref[1], 3 is not theree)</li> <li>2 -> 3 2 5 1 6 4</li> <li>3 -> 1 2 INF INF INF INF</li> </ul> <p>Similar for R_rank.</p> <p>Hospital don't have to rank everyone et can also rank less people than their capacity.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload