算法（蓝桥杯）贪心算法3——二维数组排序与贪心算法——活动选择

题目描述

学校在最近几天有 n（n≤100）个活动，这些活动都需要使用学校的大礼堂，在同一时间，礼堂只能被一个活动使。由于有些活动时间上有冲突，学校办公室人员只好让一些活动放弃使用礼堂而使用其他教室。

现在给出 nn 个活动使用礼堂的起始时间 begini​ 和结束时间 endi​ (beginii​ << endi​)，请你帮助办公室人员安排一些活动来使用礼堂，要求安排的活动尽量多。请问最多可以安排多少活动？

请注意，开始时间和结束时间均指的是某个小时的 0 分 0 秒，如：3 5，指的是 3:00~5:00 ，因此3 5和5 9这两个时间段不算冲突的时间段。

输入

第一行一个整数 n (n≤100)；

接下来的 nn 行，每行两个整数，第一个 begini​ ，第二个是 endi​ (begini​ << endi​ ≤≤ 32767)；

输出

输出最多能安排的活动数；

样例

输入

11
3 5
1 4
12 14
8 12
0 6
8 11
6 10
5 7
3 8
5 9
2 13

输出

4

知识点 

贪心算法

题解

 

（一）输入部分

Python复制

n=int(input())
a=[]
for i in range(n):
    a.append(list(map(int,input().split())))

1. n=int(input())：读取用户输入的一个整数n，表示二维数组的行数。

2. a=[]：初始化一个空列表a，用于存储二维数组。

3. for i in range(n):：通过一个循环，循环n次，每次读取一行数据。

   • a.append(list(map(int,input().split())))：读取用户输入的一行数据，使用input().split()将输入的字符串按空格分割成多个子字符串，然后通过map(int,...)将这些子字符串转换为整数，最后使用list(...)将转换后的整数构成一个列表，并将其添加到二维数组a中。

（二）排序部分

Python复制

a=sorted(a,key=lambda x: x[1])

这行代码使用Python内置的sorted函数对二维数组a进行排序。

• key=lambda x: x[1]：指定排序的关键字。这里的lambda x: x[1]是一个匿名函数，表示以二维数组中每个子列表的第二个元素（索引为1的元素，即第二列的元素）作为排序的依据。也就是说，二维数组会按照每个子列表的第二个元素的大小进行升序排序。

（三）计数部分

Python复制

sum=1
b=a[0][1]
for i in range(n):
    if a[i][1]==0:
        a[i][1]=24
    elif a[i][0]<b:
        continue
    else:
        b=a[i][1]
        sum+=1
print(sum)

1. sum=1：初始化计数器sum为1，用于记录满足特定条件的元素数量。

2. b=a[0][1]：将排序后二维数组的第一个子列表的第二个元素赋值给变量b，作为后续比较的基准值。

3. for i in range(n):：通过一个循环，遍历排序后的二维数组的每一行。

   • if a[i][1]==0:：判断当前子列表的第二个元素是否为0。

     • a[i][1]=24：如果为0，则将其修改为24。这可能是因为在特定的业务场景中，0需要被特殊处理，这里将其视为24来进行后续的比较和计数。

   • elif a[i][0]<b:：判断当前子列表的第一个元素是否小于变量b的值。

     • continue：如果是，则直接跳过当前循环，继续下一次循环。这说明如果当前元素的第一个值小于基准值b，那么它不满足计数条件，不需要进行计数。

   • else:：如果当前子列表的第二个元素不为0，且第一个元素不小于b。

     • b=a[i][1]：更新变量b的值为当前子列表的第二个元素。这是因为当前元素满足计数条件，需要将其第二个值作为新的基准值，用于后续的比较。

     • sum+=1：计数器sum加1，表示找到了一个满足条件的元素。

4. print(sum)：循环结束后，输出最终的计数结果sum。

完整代码

n=int(input())
a=[]
for i in range(n):
    a.append(list(map(int,input().split())))
a=sorted(a,key=lambda x: x[1])
sum=1
b=a[0][1]
for i in range(n):
    if a[i][1]==0:
        a[i][1]=24
    elif a[i][0]<b:
        continue
    else:
        b=a[i][1]
        sum+=1
print(sum)

总结

这段代码通过读取用户输入的二维数组，按照数组的第二列进行排序，然后根据特定条件（第一个元素不小于前一个满足条件的元素的第二个值，且第二个值不为0，若为0则视为24）对数组中的元素进行计数，最终输出满足条件的元素数量。这种处理方式在一些特定的业务场景中非常实用，例如在处理时间区间、资源分配等问题时，可以根据特定的排序和计数规则来得到所需的结果。