【算法】基于优先级的排班算法实现

场景：在大学的里，有不少社团组织会要组织中的成员值班，当然这个值班时间是学生无课的时间才会被安排值班。

假设现有如下需求：一天中有3个时间段要有人值班，每周周一到周五都要值班，就是共有15个值班段，每个时间段值班的人都不一样，现有40个学生，要求根据这些学生的无课表情况安排值班，要求每个值班段必须有两个人，每个人一周只值班一次（如果某一值班段只有一人无课，那该值班段就只能一人值班）。

小插一题，做一排列组合题：

有10个相同的糖果，颁给3个小人，要求每个人至少有2个糖果，问共有多少种分法？

（自行解答，2014年阿里实习生招有个这样的题：有10个相同的糖果，颁给3个小人，要求每个人至少有1个糖果，问共有多少种分法？）

排班算法设计的难点主要在于每个人的无课表都不一样，如果像上面的题那样的，不用根据每个人的无课表，每个人在任意一值班段都能值班，那就简单啦。

以下讲讲个人算法的设计：

1. 基于回溯法的遍历：（实现思路：当安排到第N个值班段时，发现没有满足条件的可以选，就回溯到第N-1个值班段重新安排，如果第N-1个值班段的人都试过但第N个值班段还是没有满足条件的可以选，就回溯到第N-2个值班段，以此类推不断回溯）

现将上面的问题数据量缩小下来分析下这个问题：

假设有三个值班段，三个人，根据这三个人的无课表情况给值班段安排人值班。

思路：

先在第一个值班段无课的人中选择一个人安排到该值班段值班，被安排过的人就被标志为被安排值班（flag为0表示未被安排，flag为1表示已被安排），就不能再被安排到其他值班段值班了，以此类推，安排完一个值班段就安排下一个值班段。

最好情况：

最好情况下就是安排到每个值班段都有人未被安排过值班的人，这样一次性所有就排完了，如下图：

（1、2、3表示值班段，每个值班段里的字母表示该值班段无课的人，如上面第1个值班段有A和B两个人无课，可以安排在该值班段值班）

A被安排到1值班段，

B被安排到2值班段，

C被安排到3值班段。

最坏情况：

如下图所示：

安排到第三个值班段时因为A已经被安排过值班，所以要回溯到第二个值班段重新安排，就给第二个值班段安排C值班，但此时第三个值班段还是没人可以值班，而第二个值班段的人也都遍历过了，所以此时就要回溯到第一个值班段重新安排，此时：

B被安排到1值班段，

C被安排到2值班段，

A被安排到3值班段。

上面的是基本思路，但如果对15个值班段，40个人来排班，，考虑下最坏情况，如果刚好到第十五个值班段时没人可以值班，而最后回溯到第一个值班段重新遍历，那查找比较次数都会大大增多，所以最后还是没有采取这种方法。不过个人也没能递归实现这个算法，有空再研究研究。

2. 基于优先级的选择：（实现思路：安排值班时不是从第一个值班段顺序地安排到第十五个值班段，因为在15个值班段中，有些值班段无课的人比较多，此时的选择就比较多，而有此值班段无课的人很少，那么这个值班就要优先安排人值班，比如有个值班段只有两人无课，那就要先安排这两个人在该值班段值班，这是第一个优先级；每个人一周内无课的次数都不一样，有些人一周只有一两次无课的时间，而有些人一周有五六次无课的时间，在一个值班段选择谁在该值班段值班时优先选择无课次数少的，这是第二个优先级）

// 值班段类public class DutyTime {private String time; // 值班时间private List<User> freeUsers = new ArrayList<User>(); // 该时间段无课的人private List<User> dutyUsers = new ArrayList<User>(); // 该时间段值班的人员public DutyTime(){}public DutyTime(String time) {super();this.time = time;}// 省略get set}

// 人员public class User {private String name;private int num; // 该人一周无课时间段数public User(){}public User(String name) {super();this.name = name;}// 省略get set}/** * 值班安排： * 先为每个值班段安排一名人员值班（第一轮），安排一轮后再进行第二轮、第三轮 * 按优先级安排值班： * 1.各个值班段可值班人员数少的优先安排值班 * 2.在一个值班段选择人员时，优先选择总无课次数少的人 * 注：人员在被安排后就会从该值班段中的无课人员集合中删除，这样之后就不用再遍历到；在一轮安排后开始下一轮时，每个值班段的排人顺序会重新调整（因为去掉了已被安排的人） * */public class Schedule3 {public static void main(String[] args) {User A = new User("A", 4); // A一周有4个时间段无课…DutyTime time1 = new DutyTime("1"); // 第一个值班段…time1.getFreeUsers().add(A);…List<DutyTime> dutyTimeList = new ArrayList<>();dutyTimeList.add(time1);…for (int w = 0; w < 3; w++) {// 排序，可用于值班的人数少的值班段排在前面，下面安排值班是可用于值班的人数少的值班段优先安排dutyTimeList = dutyTimeSort(dutyTimeList);// 遍历已排好序的值班段，为每个值班段安排值班人员for (int i = 0; i < dutyTimeList.size(); i++) {// 如果该值班段有无课的人才安排值班if (dutyTimeList.get(i).getFreeUsers().size() > 0) {// 得到的都是未被安排过值班的人，并排好序，总无课次数少的人排前面List<User> freeUserList = freeUserSort(dutyTimeList.get(i).getFreeUsers());// 将可在该值班段值班的人安排到该值班段值班dutyTimeList.get(i).getDutyUsers().add(freeUserList.get(0));System.out.println(freeUserList.get(0).getName() + " 被安排到" + dutyTimeList.get(i).getTime() + "值班；该值班段现有"+dutyTimeList.get(i).getDutyUsers().size()+"人值班，"+freeUserList.get(0).getName()+"一周总无课次数为："+freeUserList.get(0).getNum());// 将被安排的人从各个值班段（有该人的值班段）中删除，下次不用再遍历User delUser = freeUserList.get(0);for (int j = 0; j < dutyTimeList.size(); j++) {if (dutyTimeList.get(j).getFreeUsers().contains(delUser)) {dutyTimeList.get(j).getFreeUsers().remove(delUser);System.out.println("—"+delUser.getName()+"已从"+dutyTimeList.get(j).getTime()+"值班段删除，目前该值班段剩余未被安排人数有："+dutyTimeList.get(j).getFreeUsers().size());}}}else {System.out.println(dutyTimeList.get(i).getTime()+"该值班段已无人可安排值班");}}System.out.println("———————安排了一轮——————–");}}// 对某一值班段中无课的人进行排序（一周总无课次数少的人排在前面）public static List<User> freeUserSort(List<User> freeUserList);// 对值班段排序（可用于值班的人数少的值班段排在前面）public static List<DutyTime> dutyTimeSort(List<DutyTime> dutyTimeList);}让我们从自身的禁锢中放心地飞出去，重新审视自己，

相关文章：

你感兴趣的文章：

标签云：