每周一课：L16 Greedy algorithms(16.1)

0.png

P16.1 MaxNonoverlappingSegments

Find a maximal set of non-overlapping segments.

• P16.1 最多不重叠线段数
  找到所有不重叠集中包含线段数的最大值

线段集合中有N个线段，编号从0到n−1，每线段的起始、结束点分别在数组A和B中给出。对于每个线段I(0 ≤ I < N)，它从A[I]开始，到B[I]结束。所有线段按照结束点大小的升序排序，也就是对于K，B[K]≤B[K + 1]成立，其中0≤K<N−1。

对于两个编号不同的线段I、线段J，如果它们至少有一个公共点，也就是A[I] ≤ A[J] ≤ B[I] 或者 A[J] ≤ A[I] ≤ B[J]成立，则说明这2个线段有重叠。如果线段集合不包含两个有重叠的线段，则称此线段集是不重叠集。目标是找到不重叠集中包含的线段数的最大值。

例如，考虑数组A、B：

A[0]=1，A[1]=3，A[2]=7，A[3]=9，A[4]=9；
B[0]=5，B[1]=6，B[2]=8，B[3]=9，B[4]=10

线段集如下图所示：

image

其中不重叠集中包含线段数的最大值为3。例如，可能的集合是0、2、3；0、2、4；1、2、3或1、2、4。包含4条线段的没有不重叠集。

编写函数：

def solution(A, B)

给定由N个整数组成的两个数组A和B，则返回所有不重叠集中包含线段数的最大值。例如，给定上面所示的数组A、B，函数应该返回3。

假定：

1. N是区间[0，30,000]内的整数；
2. 数组A，B的每个元素都是区间[0，1,000,000,000]内的整数；
3. 对于I(0≤I<N)，A[I] ≤ B[I]；
4. 对于K(0≤K<N−1)，B[K] ≤ B[K + 1]；

• 解题思路

利用贪婪算法，遍历长度数组。只要线段的终点小于当前线段的起点，最终总的线段数就加1，然后更新线段的终点。如果不小于当前线段的起点，说明两条线段有重叠，然后继续判断下一条线段即可。

• Python3代码

# -*- coding：utf-8 -*-
# &Author  AnFany
# Lesson 16：Greedy algorithms
# P 16.1 MaxNonoverlappingSegments


def solution(A, B):
    """
    :param A: 线段的起始点集合
    :param B: 线段的终点集合，升序排列
    :return: 返回所有不重叠集中包含的线段数的最大值
    """
    if len(A) == 0:
        return 0
    count = 0
    end = B[0]
    for i in range(1, len(A)):
        if end < A[i]:
            count += 1
            end = B[i]
    return count + 1

• 结果

image

点击获得更多编程练习题。欢迎Follow，感谢Star!!! 扫描关注微信公众号pythonfan，获取更多。

image image