Description

N個矩形,排成一排. 現在希望用盡量少的矩形海報Cover住它們. Input

第一行給出數字N,代表有N個矩形.N在[1,250000] 下面N行,每行給出矩形的長與寬.其值在[1,1000000000]2 1/2 Postering Output

最少數量的海報數. Sample Input 5

1 2

1 3

2 2

2 5

1 4

解題思路： 單調棧的水題，維護一個遞增的單調棧，退棧時如果遇到相等，就代表可以少用一張海報。