python - 如何将 O(N*M) 优化为 O(n**2)？

Question

我正在尝试解决 USACO 的奶牛问题。问题陈述在这里:https://train.usaco.org/usacoprob2?S=milk2&a=n3lMlotUxJ1

给定二维数组形式的一系列间隔，我必须找到最长的间隔和没有发生挤奶的最长间隔。

例如。给定数组 [[500,1200],[200,900],[100,1200]]，最长间隔为 1100，因为有连续挤奶，最长间隔为 0，因为有连续挤奶没有休息时间。

我尝试过使用字典是否会减少运行时间，但没有取得太大成功。

f = open('milk2.in', 'r')
w = open('milk2.out', 'w')

#getting the input
farmers = int(f.readline().strip())
schedule = []
for i in range(farmers):
    schedule.append(f.readline().strip().split())


#schedule = data
minvalue = 0
maxvalue = 0

#getting the minimums and maximums of the data 
for time in range(farmers):
    schedule[time][0] = int(schedule[time][0])
    schedule[time][1] = int(schedule[time][1])
    if (minvalue == 0):
        minvalue = schedule[time][0]
    if (maxvalue == 0):
        maxvalue = schedule[time][1]
    minvalue = min(schedule[time][0], minvalue)
    maxvalue = max(schedule[time][1], maxvalue)

filled_thistime = 0
filled_max = 0

empty_max = 0
empty_thistime = 0

#goes through all the possible items in between the minimum and the maximum
for point in range(minvalue, maxvalue):
    isfilled = False
    #goes through all the data for each point value in order to find the best values
    for check in range(farmers):
        if point >= schedule[check][0] and point < schedule[check][1]:
            filled_thistime += 1
            empty_thistime = 0
            isfilled = True
            break
    if isfilled == False:
        filled_thistime = 0
        empty_thistime += 1
    if (filled_max < filled_thistime) : 
        filled_max = filled_thistime 
    if (empty_max < empty_thistime) : 
        empty_max = empty_thistime 
print(filled_max)
print(empty_max)
if (filled_max < filled_thistime):
    filled_max = filled_thistime

w.write(str(filled_max) + " " + str(empty_max) + "\n")
f.close()
w.close()

该程序运行良好，但我需要减少运行时间。

Answer 1

一个不太漂亮但更有效的方法是像空闲列表一样解决这个问题，尽管它有点棘手，因为范围可以重叠。此方法只需要循环输入列表一次。

def insert(start, end):
    for existing in times:
        existing_start, existing_end = existing
        # New time is a subset of existing time
        if start >= existing_start and end <= existing_end:
            return
        # New time ends during existing time
        elif end >= existing_start and end <= existing_end:
            times.remove(existing)
            return insert(start, existing_end)
        # New time starts during existing time
        elif start >= existing_start and start <= existing_end:
            # existing[1] = max(existing_end, end)
            times.remove(existing)
            return insert(existing_start, end)
        # New time is superset of existing time
        elif start <= existing_start and end >= existing_end:
            times.remove(existing)
            return insert(start, end)
    times.append([start, end])

data = [
    [500,1200],
    [200,900],
    [100,1200] 
]

times = [data[0]]
for start, end in data[1:]:
    insert(start, end)

longest_milk = 0
longest_gap = 0
for i, time in enumerate(times):
    duration = time[1] - time[0]
    if duration > longest_milk:
        longest_milk = duration
    if i != len(times) - 1 and times[i+1][0] - times[i][1] > longest_gap:
        longes_gap = times[i+1][0] - times[i][1]

print(longest_milk, longest_gap)