面试题-参加生日宴会的最多人数

本题目是字节视频面试的一道手写代码题目。本文会对这个题目进行分析，并通过代码对它进行实现。

题目描述：

2022年9月8号，小徐参加了朋友举行的生日宴会，宴会开始时间是上午10点。宴会期间，朋友想要了解一下，从宴会开始时间起，每过一个小时，宴会在席的人员数目，假设参加宴会的人入席和离席只进行一次。最后，返回在席最大人数。

案例展示

a = [1, 2, 3, 4, 5, 6]

b = [2, 4, 6, 5, 7, 10]

结果：2

a: 表示每个人入席的时间

b: 表示每个人离席的时间

例如：a[0] = 1 b[0] = 2, 表示客人在第一个时刻入席，在第二时刻离开席位。

题目分析

设dp[i]: 表示第 i 个时刻在席人的数目。

第一步：先不考虑离席时间，统计每个时刻在席人头数。

具体做法：

依次遍历列表a，对于每个值a[i]执行：

• 如果a[i] <= j, 执行 dp[j] = dp[j] + 1;  j: 表示具体时刻点。

最终得到dp[j]: 表示在不考虑离席情况下，每个时刻人头数目。

第二步：考虑离席时间，在第一步的基础上，去掉每个时刻离开席人头数。

具体做法：

依次遍历列表b，对于每个值b[i]执行：

• 如果 j>= b[i], 执行 dp[j] = dp[j] - 1;  j: 表示具体时刻点。

最终得到dp[j]: 表示在考虑离席情况下，每个时刻人头数目。

第三步：取dp列表或者数组中最大值，即为最终答案。

代码实现

a = [1, 2, 3, 4, 5, 6]
b = [2, 4, 6, 5, 7, 10]
min_in = min(a)
max_out = max(b)
dp = [0 for _ in range(max_out+1)]
 
for i in a:
    for j in range(max_out+1):
        if i <= j:
            dp[j] = dp[j] + 1
for k in b:
    for j in range(max_out+1):
        if j >= k :
            dp[j] -= 1
print(max(dp))