本文共 3551 字，大约阅读时间需要 11 分钟。

区间调动问题 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) 在可选工作中，每次选取与最小可选工作有重叠的部分。

       证明看这里?

       b)是正确的思路，因为：

       结束时间最早， 所以取相同数量的工作肯定它最早结束或至少不晚；如果后面还有工作，那么加入到结束最早算法的空间更大，因此就不会存在比它更多工作的可能。（这段话转自，这个博主的空间真的超好看了?）

       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 
   
    #include 
    
     #include 
     
      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
      
        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的排序很方便！见：。

       贪心法 - 递归版：

#include 
   
    #include 
    
     #include 
     
      using namespace std;//存储区间信息struct Val{	int start = 0;	int finish = 0;};int num;vector
      
        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 
   
    #include 
    
     #include 
     
      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
      
        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
       
         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;}
       
      
     
    
   

       动态规划的思想参考了：

转载地址：http://wxtai.baihongyu.com/