import random import time def greedyEFT(intervals): "The 'Earliest Finishing Time' Greedy Algorithm, which considers the intervals in terms of non-decreasing finishing time." # This will be the output schedule of the algorithm, represented as a list with the order being the order in which the intervals where added to the output schedule. schedule = [] # This sorts the intervals in terms of earliest finishing time. sortedIntervals = dict(sorted(intervals.items(), key=lambda e: e[1][1])) # The schedule is initialised to contain the first interval. firstInterval = list(sortedIntervals.keys())[0] schedule.append(firstInterval) # The for loop in which the algorithm schedules the remaining intervals. They are considered in terms of non-decreasing finishing time. for currInterval in sortedIntervals: currIntervalStartTime = sortedIntervals[currInterval][0] # This is the starting time of the interval we are considering for addition to the output schedule. lastIntervalFinishTime = sortedIntervals[schedule[-1]][1] # If the starting time is before the finishing time of the last interval we scheduled, then we don't add it. Note that here # the last interval to be added to the schedule is the one with the latest finishing time, so its is sufficient to only check for overlap with that. if currIntervalStartTime < lastIntervalFinishTime: # If there is an overlap, do not add the interval to the schedule. continue else: schedule.append(currInterval) # Otherwise, add it. return schedule def greedyEST(intervals): "The 'Earliest Starting Time' Greedy Algorithm, which considers the intervals in terms of non-decreasing starting time." # This will be the output schedule of the algorithm, represented as a list with the order being the order in which the intervals where added to the output schedule. schedule = [] # This sorts the intervals in terms of earliest starting time. sortedIntervals = dict(sorted(intervals.items(), key=lambda e: e[1])) # The schedule is initialised to contain the first interval. firstInterval = list(sortedIntervals.keys())[0] schedule.append(firstInterval) lastIntervalFinishTime = sortedIntervals[firstInterval][1] # The for loop in which the algorithm schedules the remaining intervals. They are considered in terms of non-decreasing starting time. for currInterval in sortedIntervals: currIntervalStartTime = sortedIntervals[currInterval][0] # This is the starting time of the interval we are considering for addition to the output schedule. if currIntervalStartTime < lastIntervalFinishTime: # If there is an overlap, do not add the interval to the schedule. continue else: schedule.append(currInterval) # Otherwise, add it. lastIntervalFinishTime = sortedIntervals[currInterval][1] # Update the latest finishing time of any interval in the output schedule to be the one of the newly added interval. Note that it is not possible for the # newly added interval to finish before any of the intervals already scheduled, as then it would not be compatible with that inteval. return schedule def greedySmallest(intervals): "The 'Smallest Interval' Greedy Algorithm, which considers the intervals in terms of non-decreasing size." # This will be the output schedule of the algorithm, represented as a list with the order being the order in which the intervals where added to the output schedule. schedule = [] # Create a new dictionary that has the interval ids as keys and their lengths as values. intervalDifferences = {} for interval in intervals: intervalDifferences[interval] = intervals[interval][1]-intervals[interval][0] # Sort the intervals in terms of non-decreasing length sortedIntervals = dict(sorted(intervalDifferences.items(), key=lambda e: e[1])) # The schedule is initialised to contain the first interval. firstInterval = list(sortedIntervals.keys())[0] schedule.append(firstInterval) # The for loop in which the algorithm schedules the remaining intervals. They are considered in terms of non-decreasing starting time. for currInterval in sortedIntervals: currIntervalStartTime = intervals[currInterval][0] # This is the starting time of the interval we are considering for addition to the output schedule. currIntervalFinishTime = intervals[currInterval][1] # This is the finishing time of the interval we are considering for addition to the output schedule. overlap = False for otherInterval in schedule: # Use variables for ease of reference when checking for overlap otherIntervalStartTime = intervals[otherInterval][0] otherIntervalFinishTime = intervals[otherInterval][1] if otherIntervalStartTime < currIntervalFinishTime and currIntervalStartTime < otherIntervalFinishTime: # If there is an overlap, do not add the interval to the schedule. overlap = True break if overlap == False: schedule.append(currInterval) # Otherwise add the interval. return schedule def greedyLargestWeight(intervals): "The 'Largest Weight Interval' Greedy Algorithm, which considers the intervals in terms of non-increasing weight." # This will be the output schedule of the algorithm, represented as a list with the order being the order in which the intervals where added to the output schedule. schedule = [] # This sorts the intervals in terms of earliest starting time. sortedIntervals = dict(reversed(sorted(intervals.items(), key=lambda e: e[1][2]))) # The schedule is initialised to contain the first interval. firstInterval = list(sortedIntervals.keys())[0] schedule.append(firstInterval) # The for loop in which the algorithm schedules the remaining intervals. They are considered in terms of non-increasing weight. for currInterval in sortedIntervals: currIntervalStartTime = intervals[currInterval][0] # This is the starting time of the interval we are considering for addition to the output schedule. currIntervalFinishTime = intervals[currInterval][1] # This is the finishing time of the interval we are considering for addition to the output schedule. overlap = False for otherInterval in schedule: # Use variables for ease of reference when checking for overlap otherIntervalStartTime = intervals[otherInterval][0] otherIntervalFinishTime = intervals[otherInterval][1] if otherIntervalStartTime < currIntervalFinishTime and currIntervalStartTime < otherIntervalFinishTime: # If there is an overlap, do not add the interval to the schedule. overlap = True break if overlap == False: schedule.append(currInterval) # Otherwise add the interval. return schedule def DP_optimal(intervals): "The 'DP_optimal' Algorithm, which finds the maximum weight intervals via dynamic programming." # Use a variable n for the number of intervals n = len(intervals) # This sorts the intervals in terms of earliest finishing time. sortedIntervals = dict(sorted(intervals.items(), key=lambda e: e[1][1])) sortedIntervals = {i: v for i, v in enumerate(sortedIntervals.values())} # Initialise a dictionary M were we will store the values of the optimal solutions to the subproblems. M = {} for interval in range(0,n): M[interval] = 0 # Initialise a list for the intervals that will be included in the optimal solution. P = [] for _ in range (0,n): P.append(False) # Set the value of M[0] to be the weight of interval 0. M[0] = sortedIntervals[0][2] # For each interval considered in non-decreasing order of finishing time for j in sortedIntervals: # Use variables for the starting and finishing time of interval j jStartTime = sortedIntervals[j][0] jFinishTime = sortedIntervals[j][1] for earlierInterval in reversed(sortedIntervals): # Use variables for ease of reference when checking for overlap earlierIntervalStartTime = sortedIntervals[earlierInterval][0] earlierIntervalFinishTime = sortedIntervals[earlierInterval][1] # Find the interval with the latest finishing time that does not overlap with j. This can be done more efficienty with binary search! if not (earlierIntervalStartTime < jFinishTime and jStartTime < earlierIntervalFinishTime): # If there is no overlap, update the value of p_j and break if earlierIntervalFinishTime <= jFinishTime: pj = earlierInterval break else: pj=-1 # pj=-1 signifies that j overlaps with all intervals # Find the weight of the current interval j jWeight = sortedIntervals[j][2] # Update the value of M[j] based on the recurrence relation if pj == -1: if j!=0: M[j] = M[j-1] else: if jWeight + M[pj] > M[j-1]: P[j] = True M[j] = max(jWeight + M[pj], M[j-1]) return M def randomIntervals(numIntervals): "A function that generates a number of intervals (given as input) uniformly at random from the [0,1] interval." intervals = {} for interval in range(0,numIntervals): a1 = random.uniform(0,1) a2 = random.uniform(0,1) # Set the smallest of the two drawn values as the starting time and the largest as the finishing time. intervals[interval] = [min(a1,a2),max(a1,a2)] return intervals def randomWeightedIntervals(numIntervals): "A function that generates a number of intervals (given as input) uniformly at random from the [0,1] interval." intervals = {} for interval in range(0,numIntervals): a1 = random.uniform(0,1) a2 = random.uniform(0,1) a3 = random.uniform(1,20) # Set the smallest of the two drawn values as the starting time and the largest as the finishing time. intervals[interval] = [min(a1,a2),max(a1,a2),a3] return intervals def experiment(K): "The main function which runs the experiment. K is the number of repeats for each value of the number of intervals. The function calculates" "the number of intervals scheduled by each of greedyEFT, greedyEST, and greedySmallest for uniform randomly generated intervals." for numIntervals in [5,10,20,50,100]: # The lists where the number of scheduled intervals for each run will be stored. numIntervalsEST = [] numIntervalsEFT = [] numIntervalsSmallest = [] for _ in range(1,K): # Repeat the experiment K times. intervals = randomIntervals(numIntervals) # Generate random intervals # Run the algorithms and compute the number of intervals they schedule. scheduledIntervalsEFT = greedyEFT(intervals) numIntervalsEFT.append(len(scheduledIntervalsEFT)) scheduledIntervalsEST = greedyEST(intervals) numIntervalsEST.append(len(scheduledIntervalsEST)) scheduledIntervalsSmallest = greedySmallest(intervals) numIntervalsSmallest.append(len(scheduledIntervalsSmallest)) # Compute the averages. averageIntervalsEST = sum(numIntervalsEST)/K averageIntervalsEFT = sum(numIntervalsEFT)/K averageIntervalsSmallest = sum(numIntervalsSmallest)/K # Prin the results on the screen print("When we have ", numIntervals, " intervals, GreedyEFT schedules on average," ,averageIntervalsEFT, " intervals.") print("When we have ", numIntervals, " intervals, GreedyEST schedules on average," ,averageIntervalsEST, " intervals.") print("When we have ", numIntervals, " intervals, GreedySmallest schedules on average," ,averageIntervalsSmallest, " intervals.") return def weighted_experiment(K): "The main function which runs the experiment. K is the number of repeats for each value of the number of intervals. The function calculates" "the number of intervals scheduled by each of the five algorithms for uniform randomly generated intervals." for numIntervals in [5,10,20,50,100]: # The lists where the number of scheduled intervals for each run will be stored. weightIntervalsEST = [] weightIntervalsEFT = [] weightIntervalsSmallest = [] weightIntervalsLargestWeight = [] weightIntervalsDP_optimal = [] for _ in range(1,K): # Repeat the experiment K times. intervals = randomWeightedIntervals(numIntervals) # Generate random intervals # Initialise running times to 0 greedyEFT_time = 0 greedyEST_time = 0 greedySmallest_time = 0 greedyLargestWeight_time = 0 DP_optimal_time = 0 # Start the timer start = time.time() # Run the algorithms and compute the number of intervals they schedule. scheduledIntervalsEFT = greedyEFT(intervals) # End the timer end = time.time() greedyEFT_time += end-start # Update the total time elapsed # Calculate the total weight of scheduled intervals totalWeight = 0 for interval in scheduledIntervalsEFT: totalWeight += intervals[interval][2] weightIntervalsEFT.append(totalWeight) # Start the timer start = time.time() scheduledIntervalsEST = greedyEST(intervals) # End the timer end = time.time() greedyEST_time += end-start # Update the total time elapsed # Calculate the total weight of scheduled intervals totalWeight = 0 for interval in scheduledIntervalsEST: totalWeight += intervals[interval][2] weightIntervalsEST.append(totalWeight) # Start the timer start = time.time() scheduledIntervalsSmallest = greedySmallest(intervals) # End the timer end = time.time() greedySmallest_time += end-start # Update the total time elapsed # Calculate the total weight of scheduled intervals totalWeight = 0 for interval in scheduledIntervalsSmallest: totalWeight += intervals[interval][2] weightIntervalsSmallest.append(totalWeight) # Start the timer start = time.time() scheduledIntervalsLargestWeight = greedyLargestWeight(intervals) # End the timer end = time.time() greedyLargestWeight_time += end-start # Update the total time elapsed # Calculate the total weight of scheduled intervals totalWeight = 0 for interval in scheduledIntervalsLargestWeight: totalWeight += intervals[interval][2] weightIntervalsLargestWeight.append(totalWeight) # Start the timer start = time.time() M = DP_optimal(intervals) # End the timer end = time.time() DP_optimal_time += end-start # Update the total time elapsed # Calculate the total weight of scheduled intervals totalWeight = 0 l=len(intervals)-1 totalWeight=M[l] weightIntervalsDP_optimal.append(totalWeight) # Compute the averages. averageIntervalsEST = sum(weightIntervalsEST)/K averageIntervalsEFT = sum(weightIntervalsEFT)/K averageIntervalsSmallest = sum(weightIntervalsSmallest)/K averageIntervalsLargestWeight = sum(weightIntervalsLargestWeight)/K averageIntervalsDP_optimal = sum(weightIntervalsDP_optimal)/K # Prin the results on the screen print("When we have ", numIntervals, " intervals, GreedyEFT schedules on average intervals of weight",averageIntervalsEFT, ".") print("When we have ", numIntervals, " intervals, GreedyEST schedules on average intervals of weight",averageIntervalsEST, ".") print("When we have ", numIntervals, " intervals, GreedySmallest schedules on average intervals of weight",averageIntervalsSmallest, ".") print("When we have ", numIntervals, " intervals, GreedyLargestWeight schedules on average intervals of weight",averageIntervalsLargestWeight, ".") print("When we have ", numIntervals, " intervals, DP_optimal schedules on average intervals of weight",averageIntervalsDP_optimal, ".") # Print the average running times print("Total Running times: \n") print("GreedyEFT: ", greedyEFT_time, "\n") print("GreedyEST: ", greedyEST_time, "\n") print("GreedySmallest: ", greedySmallest_time, "\n") print("GreedyLargestWeight: ", greedyLargestWeight_time, "\n") print("DP_optimal: ", DP_optimal_time) return weighted_experiment(1000)