Stable Marriage/Internship problem

Arunima Mandal


Assumption: The problem is usually biased toward the interns. That is – the intern’s preference is given priority. If we solve the problem by giving the priority to the teams, the solution might be different. So we’ve to make sure to understand from the problem statement – who should we give priority to – interns or teams? If not explicitly mentioned anything about this, then it will be the interns. Similarly, in case of a stable marriage problem, make sure who to give priority – men or women.

Approach: Gale–Shapley algorithm



#include<bits/stdc++.h>
using namespace std;

vector<vector<int> > stableInternships(vector<vector<int>> interns, vector<vector<int>> teams) {

  int n=interns.size();

  unordered_map<int,int> chosen_interns;
  stack<int> free_interns;
  vector<int> current_intern_choices(n+1,0);
  vector<unordered_map<int,int> > team_maps;

  for(int i=0; i<teams.size(); i++)
    {
      free_interns.push(i);
      unordered_map<int,int> rank;
      for(int j=0; j<teams[i].size(); j++) rank[teams[i][j]]=j;
      team_maps.push_back(rank);
    }
  while(!free_interns.empty())
    {
      int intern=free_interns.top();
      int preferred_team=interns[intern][current_intern_choices[intern]];
      if(!chosen_interns.count(preferred_team))
      {
        chosen_interns[preferred_team]=intern;
        free_interns.pop();
      }
      else
      {
        int prev_intern= chosen_interns[preferred_team];
        int rank_intern=team_maps[preferred_team][intern];
        int rank_prev_intern=team_maps[preferred_team][prev_intern];
        if(rank_intern<rank_prev_intern)
        {
          chosen_interns[preferred_team]=intern;
          free_interns.pop();
          free_interns.push(prev_intern);
        }
      }
      current_intern_choices[intern]++;
    }
  unordered_map<int,int>::iterator it;
  vector<vector<int> > ans;
  for(it=chosen_interns.begin(); it!=chosen_interns.end(); ++it)
    {
      vector<int> v;
      v.push_back(it->second);
      v.push_back(it->first);
      ans.push_back(v);
    }
  return ans;
}

int main()
{
    vector<vector<int> > interns={
        {0,1,2},
        {1,0,2},
        {1,2,0}
    };
    vector<vector<int> > teams={
        {2,1,0},
        {1,2,0},
        {0,2,1}
    };
    vector<vector<int> > ans=stableInternships(interns, teams);
    for(int i=0; i<ans.size(); i++)
    {
        cout<<ans[i][0]<<" "<<ans[i][1]<<endl;
    }
    cout<<endl;
    return 0;
}

Time complexity: O(N^2)

Space Complexity: O(N^2)

Leave a comment