假设你有一组人J，你需要给每个人拍照。他们只有一个摄影师，摄影师有一组有限的时间 T (|T| > |J|) 可用于拍摄每张照片.在 T 中的任何给定时间 t，摄影师只能拍摄一张照片。 J 中的每个人只能在 T 中的某个时间子集中拍照，尽管每个人都被要求至少选择一次他们有空的时间.本质上，根据每个人的可用性，摄影师想要尝试将一个人分配到 T 中的每个可用时间段，以便每个人都可以拍摄他们的照片。有多项式时间算法可以解决这个问题吗？如果不是，什么非多项式时间问题在多项式时间内简化为这个问题，即如何证明这个问题不在 P 中？
例子:
摄影师有空 [1, 12, 15, 33, 45, 77]。
A 的时间是 [12, 33]。
B 的时间是 [1, 12]。
C 的时间是 [1, 12]。
我们可以和大家合影留念:
人 A:33
乙:1
人物 C:12
如果我们一开始选择A:12，B:1，我们就找不到C的位置，即我们必须回溯并将 A 重新分配给 33。
本质上，我正在寻找一种多项式时间算法来找到合适的时间分配(如果存在)，否则能够报告不存在合适的分配。
最佳答案
这可以建模为 Assignment Problem (或 Bipartite Graph matching problem )。
来源应为人物，目的地应为摄影师可用的时间。可以通过将一个人在某个时间不可用的成本设为 1，将可用性设为 0 来构建成本矩阵。
如果矩阵不是一个方阵，则可以加上dummy people，相应的cost为0。如果人数大于次数，则为不可能分配的情况。
如果最优解的最终成本不为零，则意味着分配不可能。
可以用Hungarian Algorithm解决在多项式时间内。
关于查找唯一项目集的算法，一组项目中的每一个项目，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/20438637/