时间戳

首页 > 解决方案 > 为超过 K 位顾客在酒店找到时间

python - 为超过 K 位顾客在酒店找到时间

问题描述

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

任务是确定P期

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

3 2
5 8
2 4
3 9

输出：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

使用代码显示错误答案的问题任何人都可以提供帮助。

标签： pythonalgorithmdata-structuresgenetic-algorithm

解决方案

样本结果 (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列表是通过查看每一天并计算每天有多少客户在场而构建的。计算给定日期的客户会通过签入/签出时间 (in A) 来检查该天是否在客户的存在期内。

注意：range(inTime,outTime)以上假设不包括退房天数。将其更改为range(inTime,outTime+1)是否要包含它们

推荐阅读