http://codeup.hustoj.com/problem.php?cid=100000575&pid=0

題目描述

有一個(gè)長度為整數(shù)L(1<=L<=10000)的馬路，可以想象成數(shù)軸上長度為L的一個(gè)線段，起點(diǎn)是坐標(biāo)原點(diǎn)，在每個(gè)整數(shù)坐標(biāo)點(diǎn)有一棵樹，即在0,1,2，...，L共L+1個(gè)位置上有L+1棵樹。
??? 現(xiàn)在要移走一些樹，移走的樹的區(qū)間用一對(duì)數(shù)字表示，如 100 200表示移走從100到200之間（包括端點(diǎn)）所有的樹。
??? 可能有M(1<=M<=100)個(gè)區(qū)間，區(qū)間之間可能有重疊。現(xiàn)在要求移走所有區(qū)間的樹之后剩下的樹的個(gè)數(shù)。

輸入

兩個(gè)整數(shù)L(1<=L<=10000)和M(1<=M<=100)。
??? 接下來有M組整數(shù)，每組有一對(duì)數(shù)字。

輸出

?可能有多組輸入數(shù)據(jù)，對(duì)于每組輸入數(shù)據(jù)，輸出一個(gè)數(shù)，表示移走所有區(qū)間的樹之后剩下的樹的個(gè)數(shù)。

樣例輸入

4 2?

1 2?

0 2?

11 2?

1 5?

4 7?

0 0

樣例輸出

2?

5

*********************************************************************************************************

思路：剩余的樹，就是除了給出區(qū)間內(nèi)的樹的數(shù)量，如果直接按照移除的思路，可能會(huì)涉及到區(qū)間重復(fù)，造成了重復(fù)移除。那么就給出一個(gè)left，一個(gè)right，作為區(qū)間的起點(diǎn)和終點(diǎn)，把區(qū)間內(nèi)的樹都標(biāo)記為1，去計(jì)算標(biāo)記不為1的樹的數(shù)量即可，避免了重復(fù)移除的問題。萌新練習(xí)算法，還請(qǐng)大家多指教。