查找酒店中出现的超过 K 个客户的时间

Question

如果在任何给定时刻酒店内有超过K位顾客，则该时间段称为P期。

任务是确定P期

输入格式第一行包含 n 和 k，接下来的 n 行包含第 i 个客户的入住和退房时间测试用例：

输出：4

如果我没记错的话我们得找出此时超过K个顾客在场的时间。我的代码

def hotel(n,k,A):
    count=0
    dp=[1]*n
    for i in range(n):
        I1=A[i][0]
        o1=A[i][1]
        time=[]
        for j in range(i+1,n):
            I2=A[j][0]
            o2=A[j][1]
            if I1>=I2 and I1<o2:
                dp[i]=dp[i]+1
                if o1<=o2:
                    time.append(o1-I1)
                else:
                    time.append(o2-I1)
            elif I1<I2 and o1>I2:
                dp[i]=dp[i]+1
                if o1>o2:
                    time.append(o2-I2)
                else:
                    time.append(o1-I2)
        if dp[i]>=k:
            count+=sum(time)
    return count

使用代码显示错误答案的问题谁能帮忙

Answer 1

示例结果 (4) 表明我们正在寻找至少 K（不超过）个客户存在的总天数。问题陈述也没有具体说明退房日是包含还是不包含在期间内（对此数据给出了相同的答案，但其他样本可能有所不同）。

在任何情况下，您都可以使用列表解析和求和来计算这些值：

n = 3
K = 2
A = [(5,8),(2,4),(3,9)]

checkIns,checkOuts = zip(*A)
firstDay  = min(checkIns)
lastDay   = max(checkOuts)
counts    = [ sum(day in range(inTime,outTime) for inTime,outTime in A)
              for day in range(firstDay,lastDay+1) ]
P         = sum(count >= K for count in counts)
print(P) # 4

counts 列表是通过遍历每一天并计算每一天有多少客户而建立的。对给定日期的客户进行计数需要 check-in/check-out 次（在 A 中）以检查该天是否在客户的存在期限内。

注意：以上range(inTime,outTime)假定不包括退房日。如果要包含它们，请将其更改为 range(inTime,outTime+1)

查找酒店中出现的超过 K 个客户的时间

Find the time for more than K customers present in the hotel

python

algorithm

data-structures

genetic-algorithm