作物種植 (Plant)

發布時間: July 4, 2020, 3:37 p.m.   最後更新時間: Sept. 15, 2023, 9:46 a.m.   時間限制: 1000ms   記憶體限制: 128M

有一個農夫,在鄉間小路散步時,找到了一個很適合種農作物的黃金路段。他仔細地分析了這條路,找出每種農作物適合種植的路段。由於路上每個位置只能種植一種作物,請你撰寫一個程式幫農夫挑選作物,使得黃金路段的使用率最高(即有種植作物的位置最多)。注意:一旦挑選了作物,就必須將作物種滿整個適合種植的路段。 

輸入第一行有一個正整數M與T(1<=M,T<=10^4),M代表路段的總長度,T代表預計種植的作物有幾種。
接著T行,每行皆有兩個正整數S與E(1<=S,E<=M)代表適合種植各個作物的起始和結束位置。

請輸出有種植作物的最大位置數。

複製範例
7 3
3 4
1 3
6 7
4
複製範例
9 4
4 8
1 5
5 7
8 9
7

範例說明 1:所有作物皆種植,因此有種植作物的路段為 (1, 3)、(3, 4) 和 (6, 7),總長度為 2+1+1=4。

範例說明 2:最長作物種植路段為(1, 5)、(5, 7) 和 (8, 9),總長度為 4+2+1=7。

dp

TOI練習賽2020/06