算法入門經典關於區間覆蓋的講解：
8.4.6：區間覆蓋問題
數軸上有n個區間[ai,bi]，選擇盡量少的區間覆蓋一條指定線段[s,t]。
【分析】
突破口是區間的包含和排序掃描，不過要先進行一次預處理。每個區間在[s,t]外的部分應該首先被切除掉，因為他們的存在是沒有意義的。在預處理後，在相互包含的情況下，小區間顯然不應該考慮。
把區間按照a從小到大排序。如果區間1的七點不是s，無解，否則選擇起點在s的最長區間。選擇此區間[ai,bi]後，新的起點應該設置為bi，並且忽略所有區間在bi之前的部分，就像預處理一樣。仍然只需要一次掃描。
題意：給予幾條線段的坐標，x軸上的。求可以覆蓋[0,M]線段的最少區間數和坐標。
方法和代碼解釋：貪心，1、先排序，左坐標小到大，右坐標從大到小。確保選到的區間是最大的。
2、注意這種情況，
我們選3而不選2，這就是程序中pre_l的作用。
<喎?http://www.Bkjia.com/kf/ware/vc/" target="_blank" class="keylink">vcD4KPHA+QUO0+sLro7o8L3A+CjxwcmUgY2xhc3M9"brush:java;">#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
struct coo
{
int l;
int r;
};
const int maxn = 100000+10;
int cmp(const void *a, const void *b)
{
coo *x = (coo *)a;
coo *y = (coo *)b;
if ((*x).l == (*y).l)
return (*y).l - (*x).l;
return (*x).l - (*y).l;
}
coo p[maxn], ans[maxn];
int main()
{
#ifdef Local
freopen("a.txt", "r", stdin);
#endif
int t = 0;
cin >> t;
while (t--)
{
int M = 0, num = 0, i = 0, flag = 0;//num是坐標的數量
cin >> M;
for (num = 0;; num++)
{
cin >> p[num].l >> p[num].r;
if (p[num].l + p[num].r == 0)
break;
}
qsort(p, num, sizeof(p[0]), cmp);
int cl = 0, cr = 0, count = 0, pre_l = 0;
for (i = 0; i < num; i++)//遍歷
{
if (!i && p[i].l > 0)
{
flag = 1;
break;
}
if (p[i].r > cr)
{
cl = p[i].l;
cr = p[i].r;
}//設置為新的起點
if (i+1 < num && p[i+1].l > pre_l)
{
pre_l = cr;
ans[count].l = cl;
ans[count].r = cr;
count++;
if (cr >= M)
break;
if (p[i+1].l > cr)
{
flag = 1;
break;
}
}
if (i == num - 1)
{
if (cr < M || p[i].l > pre_l)
flag = 1;
else
{
ans[count].l = cl;
ans[count].r = cr;
count++;
}
}
}
if (flag)
cout << '0' << endl;
else
{
cout << count << endl;
for (i = 0; i < count; i++)
cout << ans[i].l << ' ' << ans[i].r << endl;
}
if (t)
cout << endl;
}
return 0;
}
錯誤：1、數組要定義在外邊，因為很大，定義在裡邊會棧溢出。
2、p[i+1].l > cr 寫錯成了 > cl 。
