我正在研究一种活动调度算法假设有N个活动。每项活动只能在指定的时间内完成（如上午8点至下午5点），完成活动需要一定的时间（如2小时）我想在一天内完成尽可能多的有开始和结束时间的活动例如。
活动1（上午8点至下午5点）需要2小时
活动2（早上7点到11点）需要1.5小时
活动3（上午11点至下午3点）需要1小时
活动4（下午1:00-3:30）需要1.5小时
活动5（早上6点到晚上8点）需要3小时
活动6（上午11点至下午6点）需要2小时
活动7（下午2点至5点）需要1小时
活动8（晚上7点至12点）需要1小时
我想从早上8点到晚上8点做尽可能多的活动。我查看了Greedy Activity Selection算法，但我的情况与此有所不同非常感谢您的帮助！
我试过这个逻辑：
Activity[] possibleActivities; // this has all the activities, Activity object has startTime, endTime and duration.
int dayStartTime= 8; //8am
int dayEndTime= 18; //6pm
Arrays.sort(possibleActivities); // sort the activities based on the startTime
int hours=dayStartTime;
List<Activity> dailyActitiy=new ArrayList<>();
for(Activity activity: possibleActivities){
if(activity.startTime<=hours && hours<dayEndTime){
dailyActitiy.add(activity);
hours+=dailyActitiy.duration;
}
}
return dailyActitiy;
最佳答案
在调度文献中，这将被称为具有可变处理时间、发布日期和到期日期的单机调度问题。这个变体是np-hard（如果我正确阅读了经典文献），因此我建议通过现成的求解器integer programming。
一个公式是为所有活动时隙对生成一个0-1变量（例如，活动2，即从上午7点到上午11点之间的1.5小时获取变量x（2,7am-8:30am）、x（2,7:30am-9am）、x（2,8am-9:30am）、x（2,8:30am-10am）、x（2,9am-10:30am）、x（2,9:30am-11am））以指示是否应在该时隙中完成该活动。目标是最大化所有这些变量的和。有两种类型的约束：对于每个活动，其变量之和最多应为一，因此每个活动最多安排一次；对于每个时间单位（在示例中为半小时），包含该单位的所有变量之和最多应为一，因此每个时刻最多有一个已安排的活动。