这个可以用Python解的算法题，你要不要来挑战一下！

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

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

for

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

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

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

表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. bestTimeToParty(schedule): 3. start = schedule[0][0] 4. end = schedule[0][1] 5. c schedule: 6. start = (c[0], start) 7. end = (c[1], end) 8. count = celebrityDensity(schedule, start, end) 9. maxcount = 0 10． i (start, end + 1): 11． count[i] > maxcount: 12． maxcount = count[i] 13． time = i 14． ('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． celebrityDensity(sched, start, end):2． count = [0] * (end + 1)3． i (start, end + 1):4． count[i] = 05． c sched:6． c[0] i:7． count[i] += 18． count

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

range

的第一个参数

start

指定的时间开始，遍历不同的时间，每次迭代后将时间

i

递增

1

。内层循环（第5～7行）遍历所有的名人，第6行代码检查当前名人当前时间是否在场。如前所述，时间必须要大于等于名人的开始时间且小于结束时间。

如果运行语句

bestTimeToParty(sched)

代码将打印

Best time to attend the party is at9o'clock : 5 celebritieswill 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． bestTimeToPartySmart(schedule):3． times = []4． c schedule:5． times.append((c[0], 'start'))6． times.append((c[1], 'end'))7． sortList(times)8． maxcount, time = chooseTime(times)9． ('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 at9.5o'clock : 5 celebritieswill be attending!

按时间进行排序怎么样？我们有一组区间列表，需要将其转换为按

'start'

和

'end'

进行标记的时间列表。接着按时间升序进行排序，并保留这些与时间关联的标签。下面是执行相关操作的代码：

1． sortList(tlist): 2． ind ((tlist) - 1): 3． iSm = ind 4． i (ind, (tlist)): 5． tlist[iSm][0] > tlist[i][0]: 6． iSm = i 7． tlist[ind], tlist[iSm] = tlist[iSm], tlist[ind]

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

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

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. chooseTime(times): 2. rcount = 0 3. maxcount = time = 0 4. t times: 5. t[1] == 'start': 6. rcount = rcount + 1 7. t[1] == 'end': 8. rcount = rcount - 1 9. rcount > maxcount:10． maxcount = rcount11． time = t[0]12． 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，为最大值。