加工生产调度（Johnson算法）

问题：

场景：工厂有n个产品，必须按顺序在A车间和B车间加工（先A后B）

目标：安排产品加工顺序，使得从开始到所有产品加工完成的总时间最短

关键限制：B车间必须等A完成后才能开始加工同一产品

上面是一个例子

它是让A的最早加工产品地加工时间尽可能地少，也就相当于降序排列。

又让B的最早加工产品的加工时间尽可能地多，也就是相当于升序排序。

但是，它不仅仅是这样做的

它是把上面地数据分成了两组，A<B放一组，A>B的放一组

对于A<B这一组按照A进行降序排列

对于A>B这一组按照B进行升序排列

至于为什么这样可以达到调度最优的问题我还是没有理解。

	sort(arr.begin(),arr.end(),[](const vector<int>&a,const vector<int>&b){
		bool a_group1 = (a[0]<=a[1]); // a是否属于group1
		bool b_group1 = (b[0]<=b[1]); // b是否属于group1
		
		if(a_group1&&b_group1)
		{
			return a[0]<b[0]; // a,b都在group1，Group1按A_i降序排列
		}
		else if(!a_group1&&!b_group1)
		{
			return a[1]>b[1]; // a,b都不在group1，Group2按B_i升序排列
		}
		else{
			return a_group1; // Group1优先于Group2
		}
		
	});

总代码：

# include<iostream>
# include<vector>
# include<algorithm>
using namespace std;

int main()
{
	int n;
	cin>>n;
	vector<vector<int>> arr(n,vector<int>(2));
	for(int i=0;i<n;i++)
	{
		cin>>arr[i][0];
	}
	
	for(int i=0;i<n;i++)
	{
		cin>>arr[i][1];
	}
	
	sort(arr.begin(),arr.end(),[](const vector<int>&a,const vector<int>&b){
		bool a_group1 = (a[0]<=a[1]); // a是否属于group1
		bool b_group1 = (b[0]<=b[1]); // b是否属于group1
		
		if(a_group1&&b_group1)
		{
			return a[0]<b[0]; // a,b都在group1，Group1按A_i降序排列
		}
		else if(!a_group1&&!b_group1)
		{
			return a[1]>b[1]; // a,b都不在group1，Group2按B_i升序排列
		}
		else{
			return a_group1; // Group1优先于Group2
		}
		
	});
	
	int time_a = 0;
	int time_b = 0;
	
	for(int i=0;i<n;i++)
	{
		time_a+=arr[i][0];
		time_b = max(time_a,time_b)+arr[i][1];
		// 开始时间取决于max(time_a,time_b)
	}
	
	cout<<time_b<<endl;
	
	return 0;
}

题目：