是否有代码可以在没有任何干扰或重叠的情况下找到最长的时间？

Question

我需要找到一个python代码来找到最大的时间段

例如：

 _________(15 days)__________
1                           15
                                                               _______(23 days)__________
                                                              100                      122
             ____________(50 days)____________
            10                              59
                                                                        ___________(70 days)___________
                                                                       115                          184

这个问题是，时间线包含了某些项目将繁忙的天数。

我想找个办法让一些东西尽可能的忙碌。

我的意思是时间线从第10天到第59天(50天)+时间线从第115天到第184天(70天)可以使项目繁忙的时间大约为120天，这是生产最长天数的最大组合。

我想从以前的时间表中提取出来：

            _____________(50 days)____________                         ___________(70 days)___________
            10                              59                         115                          184

这是字典，我把它描述为上面的时间线和干扰或重叠。

interference_dict = {
 1: {'time': 15, 'interference':[3]} ,  
 2: {'time': 23, 'interference':[4]} ,  
 3: {'time': 50, 'interference':[1]} ,  
 4: {'time': 70, 'interference':[2]}  
}

然后，我试图通过以下代码计算可能的组合时间而不受干扰：

profits = []
for schedule_id, data in interference_dict.items():
    # Generate set of interference start with selected item interference above and add the neighbour interference to it to prevent overlapping or interfering with others
    neighbour_set = set(data['interference'])

    for sub_schedule_id, sub_data in interference_dict.items():
        if sub_schedule_id not in neighbour_set:
            neighbour_set = neighbour_set.union(sub_data['interference'])

    schedule_ids = [key for key in interference_dict.keys() if key not in neighbour_set]

    if schedule_ids not in [x[1] for x in profits]:
        profits.append(
            (sum([data_['time'] for key, data_ in interference_dict.items() if key not in neighbour_set]),
             schedule_ids))
print(profits)

代码的输出:列表(不重叠项的总时间，不受干扰的项列表)

[(38, [1, 2]), (73, [2, 3]), (85, [1, 4])]

我的问题是我的代码错过了其他组合，比如(120, [3,4])。

如果有更好的方法来改进代码，我可以很容易地改变interference_dict的外观。

Answer 1

假设1.在没有干扰的情况下，任何两个附表都可以组合成有效的一对。

假设2.如果A干扰B，即A在B的干扰列表中，则相反的情况也是如此

可以使用itertools.combination获取所有可能的组合并丢弃无效的组合。

from itertools import combinations

valid_combinations = []
for a, b in interference_dict.items():
    # skip interfering combinations
    if a in interference_dict[b]["interference"]: continue
    valid_combinations.append((interference_dict[a]["time"]+interference_dict[b]["time"], [a,b]))

#Now sort be 0th value
valid_combinations.sort(key = lambda item:item[0])