We have two schedules S1&S2:
S1 = { , , ... }
S2 = { , , ... }
Assumptions:
1. S1&S2 are sorted by the starting time.
2. There are no conflicts in S1 and S2 itself.
Problem:
We try to find all the conflicts between these two schedules.
the basic idea is to merge sort to find the conflicts. the running time is
O(n).
My code in python: (code is kind of messy)
def merge(a,b):
i, j = 0, 0
unconflict = []
conflict = []
while( i < len(a) and j if(a[i][0] <= b[j][0]):
add(a[i], unconflict, conflict)
i = i + 1
else:
add(b[j], unconflict, conflict)
j = j + 1
while(i < len(a)):
add(a[i], unconflict, conflict)
i = i + 1
while(j < len(b)):
add(b[j], unconflict, conflict)
j = j + 1
def add(p, unconflict, conflict):
if len(unconflict):
if p[0] < unconflict[-1][1] :
print("Conflicts between ", unconflict[-1], p)
if len(conflict):
if p[0] < conflict[-1][1]:
print("Conflicts between ",
conflict[-1], p)
else: conflict.append(p)
else: conflict.append(p)
else:
unconflict.append(p)
if len(conflict):
if p[0] < conflict[-1][1]:
print("Conflicts between ",
conflict[-1], p)
else: unconflict.append(p)
=========================
a = [(1,2), (4,5),(6,7),(8,9),(9,10),(11,23)]
b = [(1,3),(4,8),(8,11)]
merge(a,b)
Result:
Conflicts between (1, 2) (1, 3)
Conflicts between (4, 5) (4, 8)
Conflicts between (4, 8) (6, 7)
Conflicts between (8, 9) (8, 11)
Conflicts between (8, 11) (9, 10)
