【问题1】用i表示x轴上坐标为[i-1,i]的区间（区间长度为1），并给出n个不同的整数，表示n个这样的区间。现在要求画出m条线段覆盖住所有的区间，每条线段可以任意长，要求所画线段长度之和最小。设计算法求这m条线段的最小长度和。

#include <iostream>
#include <vector>
#include<algorithm>

using namespace std;
//Data input
vector<int>vPoint;
int ShortestLine(int m)
{
	vector<int>vGap;
	int n = vPoint.size();
	if (m >= n)
		return n;

	sort(vPoint.begin(), vPoint.end());

	for (int i = 0; i < n - 1; i++)
		vGap.push_back(vPoint[i + 1] - vPoint[i] - 1);
	sort(vGap.begin(), vGap.end());

	int result = vPoint[n - 1] - vPoint[0] + 1;
	int k = vGap.size();
	for (int i = k - 1; i >= k - m + 1; i--)
	{
		if (vGap[i] > 0)
			result -= vGap[i];
	}
	return result;
}
void main(void)
{
	int n, m;
	cin >> n >> m;
	for (int i = 0; i < n; i++)
	{
		int a;
		cin >> a;
		vPoint.push_back(a);
	}
	cout << ShortestLine(m) << endl;
}

【问题2】有n个需要加工的木棍，每个木棍有长度L和重量W两个参数，机器处理第一个木棍用时1分钟，如果当前处理木棍的参数为L和W，如果之后处理的木棍L'≥L并且W'≥W,则不需要额外的时间，否则需要加时1分钟。需要求出给定木棍的最少加工时间。

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

typedef struct tagWood
{
	int len;
	int weight;

	bool operator<(const tagWood& w) const
	{
		if (len != w.len)
		{
			return len < w.len;
		}
		else
		{
			return weight < w.weight;
		}
	}
}Wood;

vector<vector<Wood>>vWoodArray;

int ShortestTime(int i)
{
	sort(vWoodArray[i].begin(), vWoodArray[i].end());

	int n = vWoodArray[i].size();

	vector<bool> bDone;
	for (int j = 0; j < n; j++)
	{
		bDone.push_back(false);
	}

	int result = 0;
	for (int j = 0; j < n; j++)
	{
		if (!bDone[j])
		{
			bDone[j] = true;
			int prev = j;
			for (int k = 0; k < n; k++)
			{
				if (!bDone[k] && vWoodArray[i][k].weight >= vWoodArray[i][prev].weight)
				{
					bDone[k] = true;
					prev = k;
				}
			}
			result += 1;
		}
	}
	return result;
}


int main()
{
	int t, n;

	cin >> t;

	for (int i = 0; i < t; i++)
	{
		int n;
		cin >> n;

		vector<Wood>vWood;
		for (int j = 0; j < n; j++)
		{
			Wood w;
			cin >> w.len >> w.weight;
			vWood.push_back(w);
		}

		vWoodArray.push_back(vWood);
	}
	cout << endl;
	
	for (int i = 0; i < vWoodArray.size(); i++)
	{
		cout << ShortestTime(i) << endl;
	}
}