将 n 个作业分配给 m 人 n>m 的算法



我正在做一个题纸生成器项目,我的系统中很少有参与者和验证器。贡献者将问题提交给我的系统,验证器将对其进行验证。那么,有没有任何特定的算法可以帮助我将问题平均分配给验证器,并且不存在与问题相关的成本。

假设您创建了分配,然后才开始处理它们,我猜简单的循环就足够了。

如果你在问题上确实有标签,那么就从排序开始。第二步是运行直到队列为空,并一次将每个问题分配给验证器。

以下是算法基础:

  1. 考虑大小为n的工作的A到蜜蜂阵列和大小为m的人的B阵列
  2. 排序数组A,例如所有的难题都将在开头
  3. 对于(0,n)中的i:将作业A[i]分配给人员B[i mod m]

遵循此算法将确保每个人都没有更多的工作——他们比另一个人多一份工作,并且在每个问题级别上他们都是均匀分布的。

如果你也可以根据人们验证问题的能力来标记他们(我的意思是,人A[i]可以更快地验证问题,他们A[j]他们还添加了排序步骤,也就是从你最快的人开始的人数组-这将导致人i比人j多出1个问题,那么可以保证他在验证过程中也更快,他们的总时间可能相等。

希望能有所帮助!

最新更新