先 排 序    <- 這 很 重 要 ， 排 序 總 能 夠 簡 化 問 題

bool cmp(line a,line b)

{

     if(a.start==b.start) return a.end<b.end;

     return a.start<b.start;

}

sort(Lines.begin(),Lines.end(),cmp);

接 下 來 ， 不 斷 在 Lines 裡 面 看 第 I 個 的 start 跟 end :

如 果 第 I 個 線 段 包 含 著 第 I + 1 個 線 段 的 start ， 而 且 第 I + 1 個 線 段 的 end > 第 I 個 線 段 的 end


就 把 第 I 個 線 段 的 end 更 新 成 第 I + 1 個 線 段 的 end 。

如 果 沒 有 包 含 到

就 直 接 算 出 原 本 的 線 段 長 ， 換 下 一 個 。

for(int i=0;i<N;i++)
{
    int s=arr[i].s,e=arr[i].e;
    while(i+1<N&&e>arr[i+1].s)
    {
         if(e<arr[i+1].e)
            e=arr[i+1].e;
         i++;
    }
    len+=e-s;
}

最 後 len 就 是 答 案 。


for(int i=0;i<N;i++)
{
    int s=arr[i].s,e=arr[i].e;
    while(i+1<N&&e>arr[i+1].s)
    {
         if(e<arr[i+1].e)
            e=arr[i+1].e;
         i++;
    }
    len+=e-s;
}

還是70%QQQQQQQQQQQQQQQQQQ

for(int i=0;i<N;i++)
{
    int s=arr[i].s,e=arr[i].e;
    while(i+1<N&&e>arr[i+1].s)
    {
         if(e<arr[i+1].e)
            e=arr[i+1].e;
         i++;
    }
    len+=e-s;
}

其實只要設定a[b]={1}，

在將輸出的片段變為0，

在全部加起來。

for(int i=0;i<N;i++)
{
    int s=arr[i].s,e=arr[i].e;
    while(i+1<N&&e>arr[i+1].s)
    {
         if(e<arr[i+1].e)
            e=arr[i+1].e;
         i++;
    }
    len+=e-s;
}

樓上的作法會TLE吧(?

排序之後用減的幾乎是O(n)

複雜度比較好