題目大意：給出N個區間[Li,Ri](1<=i<=N)，一個正整數M，求N個區間裡，並區間包含[0,M]的區間的最小個數（無解時輸出：No solution）。
Time Limit:1000MS Memory Limit:65536KB 64bit IO Format:%I64d & %I64u
數據規模：1<=M<=5000,-50000<=Li<Ri<=50000,1<=N<=99999。
理論基礎：無。
題目分析：用貪心法。
首先，預處理，除去所有可以被別的區間包含的區間，可以證明，這樣以後，得出的最優解不會劣於未處理前。
證明:假設原解用到區間[a,b]包含於[m,n]那麼將原解中的區間替換為[m,n]答案不會變劣，證畢。
還可以證明，在所有能夠覆蓋左端點的區間中選擇最靠近左端點的區間得到的解不會劣於原解。
證明：假設原解中有區間[a,b]，現有區間[m,n]，a<m由預處理知，各區間互不包含所以b<n,那麼[a,b]覆蓋的區域，[m,n]也可以將其覆蓋，因為[m,n]也可以覆蓋左端點，而n>b,所以必然也可以覆蓋右端點，這樣結果不劣於原解。所以命題得證。
貪心策略：每次找到一個區間後，將左端點更新為此區間的右端點，再進行尋找。直到找到的區間的右端點覆蓋了M為止。
最後，我們來證明這樣貪心得出的解必為最優解，假設不是最優解，那麼必然有一個區間可以去除。
1.假設此區間為第一個區間，則根據貪心策略，有第二個區間不覆蓋左端點(如果覆蓋的話，選擇的第一個區間即為此區間)，去掉第一個區間後，則左端點沒有被覆蓋，所以此區間不可去除。
2.假設此區間為最後一個區間，同1，如果去除此區間後，則右端點未被覆蓋，所以不可去除。
3.假設此區間為相鄰的三個區間[a,b],[x,y],[m,n]中的[x,y]。則根據貪心策略存在d屬於區間[x,y]有：a<x<b<m<y<n,如果去掉[x,y]，則區間[b,m]未被覆蓋，所以不可去除。
綜上所述，貪心策略所得解中所有區間都不可去除，所以必為最優解。得證。
代碼如下：
#include<iostream>
#include<cstring>
#include<string>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<queue>
#include<ctime>
#include<vector>
using namespace std;
typedef double db;
#define DBG 0
#define maa (1<<31)
#define mii ((1<<31)-1)
#define ast(b) if(DBG && !(b)) { printf("%d!!|\n", __LINE__); while(1) getchar(); } //調試
#define dout DBG && cout << __LINE__ << ">>| "
#define pr(x) #x"=" << (x) << " | "
#define mk(x) DBG && cout << __LINE__ << "**| "#x << endl
#define pra(arr, a, b) if(DBG) {\
dout<<#arr"[] |" <<endl; \
for(int i=a,i_b=b;i<=i_b;i++) cout<<"["<<i<<"]="<<arr[i]<<" |"<<((i-(a)+1)%8?" ":"\n"); \
if((b-a+1)%8) puts("");\
}
template<class T> inline bool updateMin(T& a, T b) { return a>b? a=b, true: false; }
template<class T> inline bool updateMax(T& a, T b) { return a<b? a=b, true: false; }
typedef long long LL;
typedef long unsigned int LU;
typedef long long unsigned int LLU;
#define N 100000
pair <int,int> s[N+5],pre[N+5],ans[N+5];
int m,cnt,np,na;
ostream& operator << (ostream& out,pair <int,int> a)
{
printf("%d %d\n",a.first,a.second);
return out;
}
bool fun(pair <int,int> a,pair <int,int> b)
{
if(a.first!=b.first)return a.first<b.first;
else return a.second<b.second;
}
void solve()
{
int left=0,right=m,now=0;
while(now<=np&&left<right)
{
while(now<=np&&pre[now].first<=left)now++;
if(now==0)break;
if(pre[now-1].first<=left)
{
ans[na++]=pre[now-1];
left=pre[now-1].second;
}
}
if(left>=right)
{
printf("%d\n",na);
for(int i=0;i<na;i++)cout<<ans[i];
}
else printf("No solution\n");
}
int main()
{
scanf("%d",&m);
while(1)
{
int a,b;
scanf("%d%d",&a,&b);
if(a!=0||b!=0)
{
s[cnt].first=a;
s[cnt++].second=b;
}
else break;
}
sort(s,s+cnt,fun);
pra(s,0,cnt-1)
pre[0]=s[0];
for(int i=1;i<cnt;i++)
{
if(s[i].first==pre[np].first)pre[np]=s[i];
else if(s[i].second<=pre[np].second);
else pre[++np]=s[i];
}
pra(pre,0,np)
solve();
return 0;
}
