计划具有固定开始和结束时间的最大任务数
Schedule Maximum Number Tasks That have Fixed Start and End times
我正在尝试创建一个仅使用 python built-in 模块的计划功能，这些模块将 return 非重叠约会的最大数量。该函数的输入是一个列表列表，内部列表包含 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]
如何在迭代中从原始列表中删除一个项目，然后只检查剩下的项目：
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 未涵盖的边缘情况，那么您可以轻松扩展逻辑，因为它在单独的函数中巧妙地解耦了。
类 通常稍微 slower-running 但更容易理解；您代码中的问题不是 类，而是一个糟糕的算法（您可以编写 super-optimized machine-code 冒泡排序，但它仍然很慢）。
这个问题非常适合动态规划：
按结束时间升序排列所有会议
维护一个 end-times 的列表，例如 lst[n] = t 其中 n 是会议的数量，t 是最早的 end-time这是可能的。让 lst[0] = float("-inf") 作为 no-meeting 占位符。
插入会议，找到最低的 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]
应该读作"it is possible to have at most 1 meeting ending by 1, at most 2 meetings ending by 2, at most 3 meetings ending by 3, and at most 4 meetings ending by 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
我正在尝试创建一个仅使用 python built-in 模块的计划功能，这些模块将 return 非重叠约会的最大数量。该函数的输入是一个列表列表，内部列表包含 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]
如何在迭代中从原始列表中删除一个项目，然后只检查剩下的项目：
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 未涵盖的边缘情况，那么您可以轻松扩展逻辑，因为它在单独的函数中巧妙地解耦了。
类 通常稍微 slower-running 但更容易理解；您代码中的问题不是 类，而是一个糟糕的算法（您可以编写 super-optimized machine-code 冒泡排序，但它仍然很慢）。
这个问题非常适合动态规划：
按结束时间升序排列所有会议
维护一个 end-times 的列表，例如
lst[n] = t其中n是会议的数量，t是最早的 end-time这是可能的。让lst[0] = float("-inf")作为 no-meeting 占位符。插入会议，找到最低的
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]
应该读作"it is possible to have at most 1 meeting ending by 1, at most 2 meetings ending by 2, at most 3 meetings ending by 3, and at most 4 meetings ending by 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