Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <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&lt;int&gt; 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 &lt; 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 &lt; R; i++) for (int r = i; r &gt;= 0;) { if(BestH[r] == int(R_pref[r].size())) break; const int h = R_pref[r][BestH[r]++]; if(Size[h]++ &lt; 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] &lt; 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&lt;int&gt; SH; for (int h = 0; h &lt; 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] &lt; 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",&amp;R,&amp;H); int num; // put inf for(int r = 0 ; r &lt; R ; r++) { scanf("%d",&amp;num); R_pref[r].resize(num); for(int h = 0 ; h &lt; num ; h++) { scanf("%d",&amp;R_pref[r][h]); R_rank[r][R_pref[r][h]] = h; } } for(int h = 0 ; h &lt; H ; h++) { scanf("%d",&amp;C[h]); scanf("%d",&amp;num); H_pref[h].resize(num); for(int r = 0 ; r &lt; num ; r++) { scanf("%d",&amp;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>
    singulars
    1. This table or related slice is empty.
    1. POWorker Scheduling Algorithm
      singulars
      1. PTQuestion
    1. PTAnswer
    1. USLoïc Février
    1. USLoïc Février
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. POWorker Scheduling Algorithm
      singulars
      1. PTQuestion
    1. This table or related slice is empty.
    1. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTAcceptedByOriginator
    3. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    1. CONice! I think my constraints will fit those rules. I'd go with the "hospital oriented case". A few questions on the code. 1) Where's the 1000 come from? To have an upper bound on the size of the arrays? 2) How are you using the R_pref and H_pref vectors as multi-dimensional? Looks like you're creating them as vectors with one index, but later you're calling them like R_pref[x][y]. 3) How do I pull the matching data out? That is, the hospitals and their assigned residents? Forgive me any of these questions are obvious - I've been doing Java/C# for a while and my C++ is a bit rusty!
      singulars
      1. PO
      1. USOnisemus
    2. CO1) 1000 was a upper bound for the problem I was working on (no dynamic allocation : faster and safer when you have to re-code it in under 20 minutes in a programming ontest), just use whatever you want (but be sure it's big enough). 2) Each R_pref[i] is a vector 3) In "int M" (Output data) you have the matching hospital for each resident If you have problems using it post a link to your data (and explains how it is organized) and I will build the program.
      singulars
      1. PO
      1. USLoïc Février
    3. COGotcha! I'm creating an app to test as we speak, but one example input would help a ton. Let's say Judy, who is index h=1 in the hospital list, can work Saturday at 7PM, which is r=4 in the resident list. Out of 3 possible time slots she's available to work, this is her most preferred (the other two less preferred could be...say r=1 and r=6, in that order). How would I set H_pref and R_rank to reflect that?
      singulars
      1. PO
      1. USOnisemus
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

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