安排具有固定開始和結束時間的最大數量任務

Question

我想創建一個只使用python內置模塊的計劃函數，這些模塊將返回最大數量的非重疊約會。函數的輸入是列表的列表，內部列表包含2個整數元素，開始和結束時間。開始時間和結束時間不能改變，如果一次會議的開始時間與另一次會議的結束時間相同，則不認爲它們重疊。例如：

輸入：

meetings = [[0, 1], [1, 2], [2, 3], [3, 5], [4, 5]] 
max_meetings(meetings) 

輸出：

4 

的代碼，我現在只是野蠻的力量，並在內存和執行時間瘋狂低效。儘管使用類很有趣，但似乎有更好的方法來實現它。

def max_meetings(meetings): 
    ''' 
    Return the maximum number of non overlapping meeting that I can attend 

    input: 
     meetings - A list of lists. the inner list contains 2 values, the start 
      time[0] and the end time[1]. 

    returns: 
     total - The total number of non overlapping meetings that I can attend. 
    ''' 

    num_meetings = len(meetings) 
    assert (num_meetings <= 100) 

    appt_obj = [Appt(o) for o in meetings] 

    total = 0 
    for appt in appt_obj: 
     schedule = Schedule() 
     schedule.add_meeting(appt) 
     counter = 0 
     for comp_appt in appt_obj: 
      counter += 1 
      schedule.add_meeting(comp_appt) 
      # If there isnt a chance, break to save some time 
      if ((num_meetings - counter) < (total - schedule.meetings)): 
       break 

     if schedule.meetings > total: 
      total = schedule.meetings 

    return total 


class Schedule: 
    ''' 
    A class to hold my entire schedule. Can add 
    appointments 
    ''' 
    def __init__(self): 
     self.times = set() 
     self.meetings = 0 

    def add_meeting(self, appt): 
     points = range(appt.start, appt.end) 
     if any(x in self.times for x in points): 
      pass 
     else: 
      # This for loop also seems unnecessary 
      for p in points: 
       self.times.add(p) 
      self.meetings += 1 


class Appt: 
    ''' 
    A class for an appointment 
    ''' 

    def __init__(self, meeting): 
     assert (meeting[0] >= 0) 
     assert (meeting[1] <= 1000000) 
     self.start = meeting[0] 
     self.end = meeting[1] 

Answer 1

類通常運行速度稍慢但易於理解;你的代碼中的問題不是類，它是一個糟糕的算法（你可以編寫一個超級優化的機器代碼bubblesort，它仍然很慢）。

這個問題是非常適合動態規劃：

• 排序全部結束時間

• 您升序會議保持像lst[n] = t的結束時間列表，其中n是多少的會議和t是可能的最早的結束時間。讓lst[0] = float("-inf")作爲非會議佔位符。

• 插入一個會議，發現最低n這樣lst[n] <= start，那麼如果lst[n + 1]不存在或大於end讓lst[n + 1] = end。

• 當您完成後，最大會議數量爲len(lst) - 1。

---

根據你的榜樣，

meetings = [[0, 1], [1, 2], [2, 3], [3, 5], [4, 5]] 

你應該結束了

lst = [-inf, 1, 2, 3, 5] 

應讀爲「有可能有至多會議結束最多1次，最多2次以2結尾，最多3次以3結尾，最多4次以5結尾「。

請注意，這不會告訴您哪個會議組合會給出該結果，或者有多少這樣的組合可能 - 只有至少存在一個這樣的組合。

---

編輯：嘗試以下操作：

from bisect import bisect 

class Meeting: 
    # save about 500 bytes of memory 
    # by not having a __dict__ 
    __slots__ = ("start", "end") 

    def __init__(self, start, end): 
     self.start = start 
     self.end = end 

    def __lt__(self, other): 
     return self.end < other.end 

def max_meetings(meetings): 
    meetings.sort() # Meeting.__lt__ provides a natural sort order by meeting.end 

    # -1 is just a "lower than any actual time" gatepost value 
    lst = [-1] 

    for m in meetings: 
     # find the longest chain of meetings which this meeting can follow 
     i = bisect(lst, m.start) 

     if i == len(lst): 
      # new most-meetings value 
      lst.append(m.end) 
     elif m.end < lst[i]: 
      # new earliest finish-time for 
      lst[i] = m.end 

    # what is the most meetings we can attend? 
    # print(lst) 
    return len(lst) - 1 

它運行像

meetings = [ 
    Meeting(0, 1), 
    Meeting(1, 2), 
    Meeting(2, 3), 
    Meeting(3, 5), 
    Meeting(4, 5) 
] 

print(max_meetings(meetings)) # => 4 

Answer 2

如何從迭代原來的列表中刪除的項，然後只覈查一下左：

def overlaps(one, other): 
    if one[0] <= other[0] and other[1] <= one[1]: 
     return True 
    if other[0] <= one[0] and one[1] <= other[1]: 
     return True 
    else: 
     return False 

def max_meetings(slots): 
    unique = 0 
    while len(slots) > 0: 
     meeting = slots.pop(0) 
     for slot in slots: 
      if overlaps(meeting, slot): 
       break 
     else: 
      unique +=1 
    return unique 

meetings = [[0, 1], [1, 2], [2, 3], [3, 5], [4, 5]] 
print(max_meetings(meetings)) 

如果有邊緣案件overlaps沒有涵蓋，那麼你可以擴展邏輯輕鬆，因爲它在單獨的函數中整齊地分離。