贪心算法优化
考虑一个DVR录像机能够记录电视节目的义务。 每个程序有一个开始时间和结束时间。 该DVR具有以下限制：
Consider a DVR recorder that has the duty to record television programs. Each program has a starting time and ending time. The DVR has the following restrictions:
- 在可能只能记录两个项目的一次。
- 如果它选择记录一个项目，就必须从开始录制结束。
由于电视节目和它们的起始/终止时间，是什么节目的DVR可以记录最大数量是多少？
Given the the number of television programs and their starting/ending times, what is the maximum number of programs the DVR can record?
例如：考虑6个程序： 它们被写成以下形式：
For example: Consider 6 programs: They are written in the form:
A B C。一个是程序号，b为开始时间，和c是结束时间
a b c. a is the program number, b is starting time, and c is ending time
1 0 3
2 6 7
3 3 10
4 1 5
5 2 8
6 1 9
要记录的最佳方式是有计划1和3记录背靠背，和方案2和4记录的背靠背。 2和4将被记录一起1和3。 这意味着节目的最大数量为4
The optimal way to record is have programs 1 and 3 recorded back to back, and programs 2 and 4 recorded back to back. 2 and 4 will be recording alongside 1 and 3. This means the max number of programs is 4.
什么是有效的算法来找到可以录制节目的最大数量？
What is an efficient algorithm to find the max number of programs that can be recorded?
这是一个典型的例子为贪婪算法。
This is a classic example for a greedy algorithm.
您创建一个元组在输入每个程序的数组。 现在，你解决这个数组的结束时间，并开始从左边到右边去。如果你可以把第二天的程序（您正在录制最多一个程序的话），你递增结果计数器和记忆的结束时间。对于其他程序重新填充可用插槽如果可能的话，如果没有，你不能记录，并可以将其丢弃。
You create an array with tuples for each program in the input. Now you sort this array by the end times and start going from the left to the right. If you can take the very next program (you are recording at most one program already), you increment the result counter and remember the end-time. For another program again fill the available slot if possible, if not, you can't record it and can discard it.
此方式，您将获得可记录在O（nlogn）时间节目的最大数量。
This way you will get the maximum number of programs that can be recorded in O(nlogn) time.