本文主要是介绍【算法概论】贪心算法：区间调动问题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
区间调动问题 Interval Scheling
题目描述：
Job j starts at sj and finishes at fj .
Two jobs compatible if the intervals [si，fi) and [sj，fj) do not overlap.
Goal：find maximum subset of mutually compatible jobs.
❗算法描述❗：
对于这个问题，使用贪心算法描述的话，有以下几种考虑：
a) 每次选取开始时间最早的；
b) 每次选取结束时间最早的；
c) 每次选取用时最短的；
d) 在可选工作中，每次选取与最小可选工作有重叠的部分。
证明看这里?https://blog.csdn.net/luoweifu/article/details/18195607
b)是正确的思路，因为：
结束时间最早， 所以取相同数量的工作肯定它最早结束或至少不晚；如果后面还有工作，那么加入到结束最早算法的空间更大，因此就不会存在比它更多工作的可能。（这段话转自https://www.cnblogs.com/yjlblog/p/7506887.html，这个博主的空间真的超好看了?）
so，代码的思路?
① Sort fi
② Select the first job
③ Pick the first job i such that si ≥ fj, where job j is the most recently selected job.
代码：
贪心法 - 非递归版：
#include <iostream>
#include <vector>
#include <algorithm>using namespace std;//存储区间信息
struct Val
{int start = 0;int finish = 0;
};bool comp(const Val &a, const Val &b);int main()
{int num;cout << "请输入区间个数:" << endl;cin >> num;vector<Val> vals(num);cout << "请输入各区间的起点坐标和终点坐标:" << endl;for (int i = 0; i < num; ++i){cin >> vals[i].start>> vals[i].finish;}//依据 val[i].finish 进行排序sort(vals.begin(), vals.end(), comp);/*检验排序的结果√for (int i = 0; i < num; ++i){cout << vals[i].start << vals[i].finish;}*/int temp = 0; //存储已被选入的上一区间的终点for (int i = 0; i < num; ++i){//如果区间 vals[i] 与 被选入的上一区间 没有重叠if (vals[i].start >= temp){cout << vals[i].start << ' ' << vals[i].finish << endl; //将区间 vals[i] 选入temp = vals[i].finish; //更新 temp 的值}}return 0;
}bool comp(const Val &a, const Val &b)
{return a.finish < b.finish;
}这里用到了：
① 结构体：把区间的信息定义成结构体，然后再用vector数组，真的很方便！
② 承接上面vector，这里代码首先是要根据区间终点进行排序的，vector的排序很方便！见：关于C++中vector和set使用sort方法进行排序。
贪心法 - 递归版：
#include <iostream>
#include <vector>
#include <algorithm>using namespace std;//存储区间信息
struct Val
{int start = 0;int finish = 0;
};int num;
vector<Val> vals;bool comp(const Val &a, const Val &b);
void IS_Recursive(int i, int temp);int main()
{cout << "请输入区间个数:" << endl;cin >> num;cout << "请输入各区间的起点坐标和终点坐标:" << endl;for (int i = 0; i < num; ++i){int temp1, temp2;cin >> temp1 >> temp2;Val temp;temp.start = temp1;temp.finish = temp2;vals.push_back(temp);}//依据 val[i].finish 进行排序sort(vals.begin(), vals.end(), comp);int temp = 0; //存储已被选入的上一区间的终点IS_Recursive(0, temp);return 0;
}void IS_Recursive(int i, int temp)
{if (i == num){return;}else{//如果区间 vals[i] 与 被选入的上一区间 没有重叠if (vals[i].start >= temp){cout << vals[i].start << ' ' << vals[i].finish << endl; //将区间 vals[i] 选入temp = vals[i].finish; //更新 temp 的值}IS_Recursive(i + 1, temp);}
}bool comp(const Val &a, const Val &b)
{return a.finish < b.finish;
}动态规划的版本：
#include <iostream>
#include <vector>
#include <algorithm>using namespace std;//存储区间信息
struct Val
{int start = 0;int finish = 0;
};bool comp(const Val &a, const Val &b);int main()
{int num;cout << "请输入区间个数:" << endl;cin >> num;vector<Val> vals(num);cout << "请输入各区间的起点坐标和终点坐标:" << endl;for (int i = 0; i < num; ++i){cin >> vals[i].start >> vals[i].finish;}//依据 val[i].finish 进行排序sort(vals.begin(), vals.end(), comp);//动态规划vector<int> dp(num);dp[0] = 1;for (int i = 1; i < num; ++i){int flag = 0; // flag 用于标记一段区间之前是否有其无重叠的区间,有标记为1,无标记为0//查找区间在 vals[i] 前一个无重叠的区间for (int j = i - 1; j >= 0; --j){if (vals[j].finish <= vals[i].start){dp[i] = max(dp[j] + 1, dp[i - 1]); // dp[j] + 1 表示 选择vals[i]区间，dp[i - 1] 表示 不选择vals[i]区间flag = 1;break;}}if (flag == 0){dp[i] = 1; //如果第 i 区间之前没有不重叠的区间，则dp[i] = 1}}cout << dp[num - 1] << endl;return 0;
}bool comp(const Val &a, const Val &b)
{return a.finish < b.finish;
}动态规划的思想参考了：【动态规划-贪心】区间调度问题
这篇关于【算法概论】贪心算法：区间调动问题的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
