Is there a code to find the longest period of time without out any interference or overlapping?

user_13570772 0
Viewed 85

I need to find a python code to find biggest periods of time doesn't matter the gaps.

For example:

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

This problem is the time line contains the days that some item will be busy.
I want to find a way to make some item as busy as possible.
Well I mean the timeline from day 10 to day 59 (50 days) + the time line from day 115 to day 184 (70 day) can make item busy for about 120 days which is the largest combination to produce longest days.

I want to extract that from the previous timeline:

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



This is the dictionary which I represented as a timeline above and the interference or overlapping.

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

Then I tried to calculate possible combinations time without interference by the following code:

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)

The output of the code: list of (total time of non overlapping items, list of items not interfered)

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

My problem that my code miss other combinations like (120, [3,4]).
If there is a better way to improve code I can easily change how interference_dict looks.

python
1 Answers

Assumption 1. Any two schedules can be combined into a valid pair so far as there is no interference.
Assumption 2. If A interferes with B, i.e., A is in B's interference list, The opposite is also true

You can use itertools.combination to get all possible combinations and discard the invalid combinations.

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])
user_95047490
Related