[Algorithm] Stable internships
A company has hired N interns to each join one of N different teams. Each intern has ranked their preferences for which teams they wish to join, and each team has ranked their preferences for which interns they prefer.
Given these preferences, assign 1 intern to each team. These assignments should be "stable," meaning that there is no unmatched pair of an intern and a team such that both that intern and that team would prefer they be matched with each other.
In the case there are multiple valid stable matchings, the solution that is most optimal for the interns should be chosen (i.e. every intern should be matched with the best team possible for them).
Your function should take in 2 2-dimensional lists, one for interns and one for teams. Each inner list represents a single intern or team's preferences, ranked from most preferable to least preferable. These lists will always be of length N, with integers as elements. Each of these integers corresponds to the index of the team/intern being ranked. Your function should return a 2-dimensional list of matchings in no particular order. Each matching should be in the format [internIndex, teamIndex].
Sample Input
interns = [
[0, 1, 2],
[1, 0, 2],
[1, 2, 0]
]
teams = [
[2, 1, 0],
[1, 2, 0],
[0, 2, 1]
]
Sample Output
// This is the most optimal solution for interns
[
[0, 0],
[1, 1],
[2, 2]
]
// This is also a stable matching, but it is suboptimal for the interns
// because interns 0 and 2 could have been given better team matchings
[
[2, 0],
[1, 1],
[0, 2]
]
Solution
// Intern - leading factor
// Team - side factor
function stableInternships(leadingFactor, sidefactor) {
const res = {}
const sideRanks = sidefactor.map(side => {
return side.reduce((acc, curr, i) => {
acc[curr] = i
return acc
}, {})
})
const spots = [...new Array(leadingFactor.length)].map((_, i) => i)
const rounds = [...new Array(leadingFactor.length)].fill(0)
while (spots.length > 0) {
const leadingIndex = spots.pop()
const leadingPickSide = leadingFactor[leadingIndex][rounds[leadingIndex]]
rounds[leadingIndex] += 1
if (!(leadingPickSide in res)) {
res[leadingPickSide] = leadingIndex
continue
}
const previousLeadingRank = sideRanks[leadingPickSide][res[leadingPickSide]]
const currentLeadingRank = sideRanks[leadingPickSide][leadingIndex]
if (previousLeadingRank < currentLeadingRank) {
spots.push(leadingIndex)
} else {
spots.push(res[leadingPickSide])
res[leadingPickSide] = leadingIndex
}
}
return Object.entries(res).map(([side, leading]) => {
return [leading, parseInt(side)]
});
}
// Do not edit the line below.
exports.stableInternships = stableInternships;
O(n^2) time | O(n^2) space - where n is the number of interns
相关文章
- [Machine Learning] Backpropagation Algorithm
- [Algorithm] BFS vs DFS
- [Algorithm] Inorder Successor in a binary search tree
- [Algorithm] Tree: Lowest Common Ancestor
- [Algorithm] Reverse array of Chars by word
- [Algorithm] Maximum Contiguous Subarray algorithm implementation using TypeScript / JavaScript
- [Algorithm] Disk height (DP + back tracking)
- [Algorithm] Stable internships
- [Algorithm] Convert a number from decimal to binary
- [Algorithm] Dynamic programming: Find Sets Of Numbers That Add Up To 16
- [Algorithm] Maximum Contiguous Subarray algorithm implementation using TypeScript / JavaScript
- [Algorithm] Median Maintenance algorithm implementation using TypeScript / JavaScript
- Algorithm:数学建模大赛(CUMCM/NPMCM)之数学建模(经验/技巧)、流程(模型准备/模型假设/建模/求解/分析/优化/预测/评价)、论文写作(意义/摘要/关键词/问题重述和模型假设/建
- Dijkstra's Algorithm
- Algorithm:网络广告营销领域之归因分析/归因模型的简介、算法、案例应用之详细攻略
- Algorithm:数学建模大赛(CUMCM/NPMCM)之全国大学生数学建模竞赛历年考察知识点统计可视化分析、论文评阅标准参考、国内外CUMCM数学建模类参考文献论文集合之详细攻略
- 论文解读(Cluster-GCN)《Cluster-GCN: An Efficient Algorithm for Training Deep and Large Graph Convolutional Networks》