递归调度算法不能正常工作

Question

我创建了一个递归调度算法，它接受一个包含开始时间和结束时间的事件对象数组。这些时间是随机生成的，开始时间总是小于结束时间。时间是0-24之间的数字（一天24小时，24==0）

以下是随机事件数组生成器的代码：

def randomEventArray(s):
    e = []
    rand1 = 0
    rand2 = 0
    for i in range(s):
        rand1 = random.randint(0,21)
        rand2 = random.randint(rand1+1,23)
        e.append(Event(rand1,rand2))
    return e

下面是事件对象的代码：

class Event:
    def __init__(self, start, end):
        self.startTime = start
        self.endTime = end
    def __repr__(self):
        return str(self)
    def __str__(self):
        return (str([self.startTime,self.endTime]))

现在是引起问题的部分。我已经创建了一段代码，它递归地遍历生成的事件数组，并列出了在一个24小时内可以保存的大多数事件。任何事件都不应重叠。你知道吗

下面是创建的递归贪婪算法：

def scheduleGD2(E):
    events = []
    scheduleRecGD2(E,0,0, events)

    return events[:]

def scheduleRecGD2(E, eventPos, startTime,events):

    while eventPos < len(E) and E[eventPos].startTime < startTime:

        eventPos += 1
    if eventPos == len(E):
        return []
    minEndPos = eventPos
    for i in range(eventPos+1, len(E)):
        if E[i].endTime < E[minEndPos].endTime:
            minEndPos = i
    events.append(E[minEndPos])
    return scheduleRecGD2(E, minEndPos+1, E[minEndPos].endTime, events)

E = randomEventArray(20)
print(scheduleGD2(E))

该算法的预期输出是一个数组，其中最多的事件可以在一个24小时内同时发生而不重叠。e、 g

[[0, 1], [1, 3], [4, 8], [9, 17], [17, 24]]

但是，我收到以下输出：

[[0, 1], [12, 16], [12, 16], [5, 17], [21, 22]]

它清楚地显示了Arr[2]与Arr[1]（Arr[2].StartTime（12）<；Arr[1].EndTime[16]）的重叠，这不应该发生。你知道吗

怎么了？为什么会这样？你知道吗

Answer 1

我为调试插入了代码，包括用简单的成对元组替换事件包。你知道吗

def scheduleRecGD2(E, eventPos, startTime, events):
    print("ENTER Rec", "eventPos", eventPos, "\tstartTime", startTime, "\n\tevents", events)

    while eventPos < len(E) and E[eventPos][0] < startTime:
        eventPos += 1

    if eventPos == len(E):
        return []

    minEndPos = eventPos
    print("\tFIRST: minEndPos", minEndPos, E[minEndPos])

    for i in range(eventPos+1, len(E)):
        if E[i][1] < E[minEndPos][1]:
            minEndPos = i 

    events.append(E[minEndPos])
    print("\tTRACE: minEndPos", minEndPos, E[minEndPos])

    return scheduleRecGD2(E, minEndPos+1, E[minEndPos][1], events)

# Main program
E = randomEventArray(8)
print(E)
print(scheduleGD2(E)) 

输出：

[(15, 20), (4, 7), (17, 20), (18, 23), (2, 7), (8, 23), (15, 23), (18, 20)]
ENTER Rec eventPos 0    startTime 0 
    events []
    FIRST: minEndPos 0 (15, 20)
    TRACE: minEndPos 1 (4, 7)
ENTER Rec eventPos 2    startTime 7 
    events [(4, 7)]
    FIRST: minEndPos 2 (17, 20)
    TRACE: minEndPos 4 (2, 7)
ENTER Rec eventPos 5    startTime 7 
    events [(4, 7), (2, 7)]
    FIRST: minEndPos 5 (8, 23)
    TRACE: minEndPos 7 (18, 20)
ENTER Rec eventPos 8    startTime 20 
    events [(4, 7), (2, 7), (18, 20)]
[(4, 7), (2, 7), (18, 20)]

---

分析

你的算法不止一次的自我崩溃。最重要的是，当你第二次进入程序时，你会发现第一个记录有一个可接受的开始时间，并把它的结束时间作为“要拍的数字”。从那时起，您将完全忽略调用中给定的开始时间，以及其余事件的开始时间，只查找比相对任意间隔的结束时间快的事件。你知道吗

您可以这样继续浏览列表，随意更改给定的开始时间，直到到达列表的末尾。你知道吗

---

修理

遵循网上提供的许多解决方案：首先，按结束时间排序，然后按开始时间排序。现在，浏览列表很简单，找到第一个可用的开始时间（a）比最近添加的元组晚；（b）不少于当前结束时间。你知道吗

考虑到解决方案的可用性，我将把这个留给学生做练习。从随机化程序的简单改变开始：

return sorted(e)