谜题：参加派对的最佳时间

本谜题涵盖的程序结构和算法范型：元组、元组列表、嵌套for

循环和浮点数、列表切片、排序。

你在办公室抽奖中赢得了一张奖票，去参加一场名人庆祝派对。由于门票的需求量很高，你只能待一个小时，但是由于拥有一张特等票，因此你可以选择在哪个小时出席。你有一张时间表，上面准确地列有每位名人出席派对的时间，你希望与尽可能多的名人合影来提高你的社会地位。这意味着你需要在特定的某个时段出席派对，这样你可以和最多的名人交谈，并获得与他们每个人的自拍。

表2-1给出的是一个例子。

参加派对的最佳时间是几点？或者说，你应在哪个时间参加派对？

通过查看每个小时并计算名人的数量，你可能发现如果在10点到11点之间参加，将得到与Brad、Katy和Drake的自拍。没有比得到3张自拍更好的了。

谜1　反复检查时间

下面是算法的代码：

 1. sched = [(6, 8), (6, 12), (6, 7), (7, 8),
 (7, 10), (8, 9), (8, 10), (9, 12),
 (9, 10), (10, 11), (10, 12), (11, 12)]
 2. def bestTimeToParty(schedule):
 3. start = schedule[0][0]
 4. end = schedule[0][1]
 5. for c in schedule:
 6. start = min(c[0], start)
 7. end = max(c[1], end)
 8. count = celebrityDensity(schedule, start, end)
 9. maxcount = 0
10． for i in range(start, end + 1):
11． if count[i] > maxcount:
12． maxcount = count[i]
13． time = i
14． print ('Best time to attend the party is at',
 time, 'o\'clock', ':', maxcount,
 'celebrities will be attending!')

算法的输入是一个时间表，也就是一组区间的列表。每段区间是一个二元组，其中的两个元素都是数字。第一个元素是开始时间，第二个元素是结束时间。该算法不能修改这些区间，因此用元组来表示。

第3～7行代码确定名人出席派对的最早时间与最晚时间。代码第3行和第4行假定schedule中至少有一个元组，用该元组初始化变量start和end。我们希望变量start表示每位名人最早开始时间，变量end表示每位名人的最晚结束时间。schedule[0]给出schedule的第一个元组。访问这个元组的两个元素的方式和访问列表中的元素完全相同。由于schedule[0]为元组，我们需要另外一个[0]用于访问元组的第一个元素（第3行代码），[1]用于访问元组的第二个元素（第4行代码）。

在for

循环中会遍历列表中的所有元组，将其中的每个元组命名为c。注意，如果我们将c[0]修改为10（例如），程序会抛出错误，因为c是元组。另一方面，如果声明sched = [[6, 8], [6, 12], ...]，我们便可以将6改为10（例如），因为sched中的每个元素都是列表。

第8行代码调用一个函数，填充列表count，用于表示start和end时间范围内每一小时内在场的名人数量。

第9～13行代码用于找出最大的名人数量出席的时段，循环start到end时间范围内的各个小时，通过变量maxcount跟踪最大的名人数量。这些代码可以替换为：

 9a. maxcount = max(count[start:end + 1])
10a. time = count.index(maxcount)

Python提供了一个函数max

可用于查找列表中的最大元素。此外，我们可以使用切片（slice）来选取列表中一段特定连续范围内的元素。在第9a行中，我们找到索引start和end之间（包含end）的最大元素。如果有b = a[0:3]，意思是将a的前3个元素（即a[0]、a[1]、a[2]）复制到列表b中，其长度为3。第10a行确定最大元素的索引。

下面是算法的核心内容，实现在函数celebrityDensity中：

1． def celebrityDensity(sched, start, end):
2． count = [0] * (end + 1)
3． for i in range(start, end + 1):
4． count[i] = 0
5． for c in sched:
6． if c[0] <= i and c[1] > i:
7． count[i] += 1
8． return count

这一函数包含一个嵌套循环。外层循环从range

的第一个参数start指定的时间开始，遍历不同的时间，每次迭代后将时间i递增1。内层循环（第5～7行）遍历所有的名人，第6行代码检查当前名人当前时间是否在场。如前所述，时间必须要大于等于名人的开始时间且小于结束时间。

如果运行语句

bestTimeToParty(sched)

代码将打印

Best time to attend the party is at 9 o'clock : 5 celebrities 
will be attending!

这一算法看起来似乎很合理，但是有一点不能令人满意。时间单位是什么？在我们的例子中，可以假设6代表下午6点，11代表下午11点，12代表上午12点，这意味着时间的单位是1小时。但是如果名人像他们习惯的那样，在任意时间来去将会怎么样呢？例如，假设Beyoncé在6:31到场并在6:42离开，Taylor在6:55到场并在7:14离开。我们可以将时间单位设为1分钟而非1小时。这意味着在第6行循环中要执行60次检查。如果碧昂丝（Beyoncé）选择在6:31:15到场，我们就该要检查每一秒。名人到达和离开的时间单位也可能在毫秒级（好吧，即使是Beyoncé，这也很难做到）！时间单位不得不做出选择，很烦人。

你能想出一个不需要依赖时间精度的算法吗？这一算法应该利用大量只与名人的数量相关而与他们的日程安排无关的操作。

题2　聪明地检查时间

我们绘图表示所有名人的区间，以时间为横轴。图2-1是一种可能的名人日程表。

图2-1

这张图片耐人回味—— 它告诉我们，如果在特定时间拿一把“标尺”（如图2-1中的虚线所示），就可以计量与标尺相交的名人时间区间个数，从而得知这时可以见面的名人数量。在前面的简单算法中，我们早已得知名人数量，也编写了相关代码。但是可以从图中额外观察到以下两点。

（1）我们只需要关心名人时间区间的起点和终点，因为只有这些时刻在场名人数量才会发生变化。没有必要计算第二条虚线时间在场的名人数量——它和第一条虚线完全相同，因为在第一条和第二条虚线或时间范围内，没有新的名人到达或者离开（回忆一下，第4位名人——从上往下数第4条线——在第一条虚线对应的时间便已到达派对现场了）。

（2）我们可以将标尺从左侧向右侧移动，通过增量计算找出名人数量最多的时间，这一点将在下面详述。

我们保存名人的计数，初始为零。每当看到名人时间区间的开始时间，便递增这个计数，每当看到名人时间区间的结束时间，便递减这个计数。我们同时也跟踪最大的名人数量。名人数量在名人时间区间的开始和结束时发生变化，而最大的名人数仅在名人时间区间的开始时间发生变化。

这里有一个关键点，我们必须随着时间的增加来执行这一计算，从而模拟标尺从左往右移动。这意味着必须对名人日程表的开始时间和结束时间进行排序。我们在上面的图片中，想首先看出第二位名人的开始时间，然后是第三位名人的开始时间，再是第一位名人的开始时间，依此类推。我们稍后会操心怎样对这些时间进行排序，但现在先来看看如下代码，这段代码会以更高效和优雅的方式来发现参加派对的最佳时间。

1． sched2 = [(6.0, 8.0), (6.5, 12.0), (6.5, 7.0),
 (7.0, 8.0), (7.5, 10.0), (8.0, 9.0),
 (8.0, 10.0), (9.0, 12.0), (9.5, 10.0),
 (10.0, 11.0), (10.0, 12.0), (11.0, 12.0)]
2． def bestTimeToPartySmart(schedule):
3． times = []
4． for c in schedule:
5． times.append((c[0], 'start'))
6． times.append((c[1], 'end'))
7． sortList(times)
8． maxcount, time = chooseTime(times)
9． print ('Best time to attend the party is at',
 time, 'o\'clock', ':', maxcount,
 'celebrities will be attending!')

注意，schedule和sched2是二元组的列表，如前所述，每个元组的第一个元素是开始时间，第二个元素是结束时间。但是在sched2中用浮点数而非在schedule中用整数来表示时间。6.0、8.0等数字都是浮点数。在这道谜题中，我们仅比较这些数字，没有必要对它们执行其他算术操作。

另一方面，在第3行被初始化为空的列表times是二元组的列表，每个元组的第一个元素是时间，第二个元素是用来指示时间是开始时间还是结束时间的字符串标记。

第3～6行代码收集所有名人的开始时间和结束时间，每次都做这样的标记。列表未经排序，因为我们不能假定参数schedule曾按任何方式排过序。

第7行代码通过调用一个排序过程对列表进行排序，稍后我们会介绍这个排序过程。一旦列表经过排序，第8行代码会调用关键的过程chooseTime，用以执行增量计算来确定各个时间段内名人的数量（密度）。

这段代码将会按与打印原始时间表sched相同的方式，打印出sched2：

Best time to attend the party is at 9.5 o'clock : 5 celebrities
will be attending!

按时间进行排序怎么样？我们有一组区间列表，需要将其转换为按'start'和'end'进行标记的时间列表。接着按时间升序进行排序，并保留这些与时间关联的标签。下面是执行相关操作的代码：

1． def sortList(tlist):
2． for ind in range(len(tlist) - 1):
3． iSm = ind
4． for i in range(ind, len(tlist)):
5． if tlist[iSm][0] > tlist[i][0]:
6． iSm = i
7． tlist[ind], tlist[iSm] = tlist[iSm], tlist[ind]

这段代码是如何工作的？它对应于可能是最简单的排序算法——选择排序[1]

。该算法找到最小的时间，并在外层for

循环的第一次迭代之后（第2～7行），将其放在列表的起始位置。对最小值的搜索需要len(tlist) - 1

次计算而非len(tlist)

次计算，因为我们在仅剩一个元素时不需要仍找寻最小值。

寻找最小元素需要遍历列表的所有元素，执行于内层for

循环（第4～6行）。因为列表起始位置已经有元素存在，该元素需要保留在列表中的其他某位置，所以算法在第7行代码将两个元素交换。可将第7行代码理解为并行发生的两次赋值：tlist[ind]获取tlist[iSm]的旧值，tlist[iSm]获取tlist[ind]的旧值。

在外层for

循环的第二轮迭代中，算法查看列表中的其余条目（不包含第一个条目），找出最小值，通过在迭代中将最小值与当前第二位的元素交换，将最小值作为第一个条目后的第二个条目放置。注意，第4行代码range

有两个参数，确保在外层循环的每次迭代中，内层循环都以ind开始，这样可以确保索引小于ind的元素都保持在正确的位置。这一过程持续到列表中所有的元素完成排序为止。因为参数列表中每个元素都是一个二元组，我们必须在第5行的比较中使用二元组第一项的时间值，这便是我们在第5行中使用额外的[0]的原因。当然，我们是在对二元组进行排序，第7行代码交换的是二元组，'start'和'end'标签依然附着在原来的时间上。

一旦列表完成排序，过程chooseTime（如下所示）会通过单次遍历列表确定最佳时间和该时间的名人数量。

 1. def chooseTime(times):
 2. rcount = 0
 3. maxcount = time = 0
 4. for t in times:
 5. if t[1] == 'start':
 6. rcount = rcount + 1
 7. elif t[1] == 'end':
 8. rcount = rcount - 1
 9. if rcount > maxcount:
10． maxcount = rcount
11． time = t[0]
12． return maxcount, time

迭代次数是名人数量的两倍，因为列表times中有两个条目（每个都是二元组），分别对应每位名人的开始时间和结束时间。将该算法和前面双层嵌套循环的简单算法进行比较，简单的算法的迭代次数等于名人的数量乘以小时数（或者根据具体情况为分钟数或秒数）。

注意，参加派对的最佳时间往往和某些名人到达派对的开始时间相对应，这是由于rcount仅在这些开始时间递增，因而在这些时间之一达到峰值。我们将在习题2中利用这一观察结果。

3　有序的表示

4　习题

习题1　

假设你是一位非常忙碌的名人，并不能自由选择参加派对的时间。对过程增加参数并修改，使它能够在给定的时间范围ystart和yend内，确定能见到最多多少位名人。与名人一样，你的时间区间为 [ystart,yend)，表示你会在任意满足ystart≤t＜yend 的时间t时在场。

习题2　

有另一种方法，可以不依赖时间精度来计算参加派对的最佳时间。我们依次选择每位名人的时间区间，并确定有多少其他名人的时间区间包含所选名人的开始时间。我们选择出某位名人，使他的开始时间被最大数量的其他名人时间区间所包含，并将他的开始时间作为参加派对的时间。编写代码实现该算法，并验证它的结果与基于排序算法的结果是否相同。

难题3　

假设每位名人都有一个权重，取决于你对这位名人的喜爱程度。可以在时间表中将其表示为一个三元组，如(6.0, 8.0, 3)。开始时间是6.0，结束时间是8.0，权重是3。修改代码，找出最大化名人总权重的时间。例如，给定图2-2，我们想要返回与右侧虚线对应的时间，即使当时只有两位名人。

图2-2

因为这两位名人对应的权重为4，大于第一条虚线时在场的3位名人对应的权重3。

下面是一个更复杂的例子：

sched3 = [(6.0, 8.0, 2), (6.5, 12.0, 1), (6.5, 7.0, 2),
 (7.0, 8.0, 2), (7.5, 10.0, 3), (8.0, 9.0, 2),
 (8.0, 10.0, 1), (9.0, 12.0, 2),
 (9.5, 10.0, 4), (10.0, 11.0, 2),
 (10.0, 12.0, 3), (11.0, 12.0, 7)]

根据名人的日程安排，你想要在11点参加派对，此时参加派对名人权重之和是13，为最大值。

[1]　不一定是最高效的算法，但最容易编写与理解。在谜题11与谜题13中，我们将会见到更好的排序算法。

本文摘自最新上架的《编程的乐趣 用Python解算法谜题》

这本书正在参加满１００减５０的活动，活动截止至６月３日，需要的朋友请抓住机会。

本书中每个谜题的开始都会介绍一道谜题，其中不少谜题都脍炙人口，以各种变体形式在一些出版物和网站上出现过。在经历一两次失败的解谜尝试之后，突然灵光一闪，一种搜索策略、一个数据结构、一个数学公式跃然而出，答案就这么自行现身了。有时候会对谜题给出明显“暴力”的解法，本书会先解释相关的算法与代码，再将其解释为“失败”，然后再“捧出真经”，引出更加优雅和高效的解法。