区间调度之贪心算法解法
区间调度问题，或者说是活动安排问题，在实际中用途非常广泛。解决这个问题的核心思想其实比较简单，可以说是一种贪心算法的思想，是贪心算法的一个很典型的应用。这里主要记录一些和解决这个问题相关的问题。
问题分析
首先看一下问题描述：
给你很多形如 `[start, end]` 的闭区间，请你设计一个算法，**算出这些区间中最多有几个互不相交的区间**。
这种问题可能有很多的说法，比如活动安排，开会，重叠区间等等，但是本质上都是这样一个问题。这种问题的解法在学校也早已学过了，这里就不在多去分析。
解决该类问题的一个非常有效的步骤就是：
- 首先将所有区间按照
end进行排序 - 选择end最小的区间 x，将所有与x重合的区间删除
- 重复上述过程，知道所有区间都被选择（删除），选出的x就是最大不相交区间
到这里，问题就已经被解决了，再有类似的问题也不过是在这个思路的基础上变化一下。但是我在实际的编码过程中却遇到了一些问题。
代码实现
由于我是最近才选择用python来做算法题，所以对python这方面相关的函数还是不够了解，在这里便遇到了一个坑处。在C++里，我们想对sort函数进行自定义，只需要自己定义一个函数，来描述出所想要的“大小关系”即可。但是在python里却不是这么实现的。
python的sorted函数
在遇到上述问题后，我大概的收集了一下资料。我发现在python2里，sorted函数的用法还是和C++是相同的，但是在python3里却进行了改变（据说是可以提高性能，但是都用python了还讲啥性能.jpg）。在python3的sorted函数中，原来接受比较函数的参数改为了key参数。这个参数只接受 一个单参数的函数作为参数（此处可能比较绕，具体代码解释），因此需要接触python的functools包来解决这个问题。看具体代码：
import functools
def cmp(a: list, b:list) -> int: # 一般的比较函数 在此处定义“大小关系”即可
return a[1] - b[1]
l = sorted(l, key=functools.cmp_to_key(cmp))
# key参数只接受一个单参数的函数 functools.cmp_to_key()将cmp函数转化为一个单参数的函数，换句话说，将list l 中的所有元素都转化成了按照cmp关系定义的可比较的元素。查询到的资料是这样描述的：
functools.cmp_to_key(func)将老式的比较函数（comparison function）转化为关键字函数（key function）。与接受 key function 的工具一同使用（如 sorted(), min(), max(), heapq.nlargest(), itertools.groupby())。该函数主要用来将程序转成 Python 3 格式的，因为 Python 3 中不支持比较函数。比较函数是可调用的，接受两个参数，比较这两个参数并根据他们的大小关系返回负值、零或正值中的某一个。关键字函数也是可调用的，接受一个参数，同时返回一个可以用作排序关键字的值。
到这里这个问题才算完全解决了，下面给出这个问题的完整代码，也可以作为其他类似问题的一个模板或者基础。
import functools
def cmp(a: list, b: list) -> int:
return a[1] - b[1]
def intervalSchedule(intvs: [[]]):
if len(intvs) == 0:
return 0
intvs = sorted(intvs, key=functools.cmp_to_key(cmp))
count = 1
x_end = intvs[0][1]
for inter in intvs:
start = inter[0]
if start > x_end:
count += 1
x_end = inter[1]
return count小结
最近两天都没有更新，实属偷懒了哈哈哈（netflix.jpg)真香。在家学习总是没有效率，每次连续的学习时间都不会超过半个小时，我想主要是因为没有显示器的原因吧hhh 只能说是尽量改变吧 在家 能学多少学多少😁
