Description：

一排 $n$ 个矩形，用尽量少的矩形不重叠的覆盖他们。

$1\le n \le 250000$

Solution：

首先把每个矩形只用一个矩形覆盖，这样就要用 $n$ 个矩形，然后可以把两个等高的且中间没有比他们低的矩形的两个矩形用一张海报覆盖，找这个的过程可以用单调栈实现，即维护一个单调递增的栈，每次加入一个新元素时不停把比他高的都弹掉，如果最后一个和他高度相同，那么就可以少用一个，答案 $-1$ 。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

int n;

#define MAXN 250010

int len[MAXN],hei[MAXN];

int s[MAXN],top = 0;

int main()

{

	scanf("%d",&n);

	for(int i = 1;i <= n;++i)

	{

		scanf("%d%d",&len[i],&hei[i]);

	}

	int ans = n;

	for(int i = 1;i <= n;++i)

	{

		while(top != 0 && hei[s[top]] >= hei[i])

		{

			if(hei[s[top]] == hei[i])--ans;

			--top;

		}

		s[++top] = i;

	}

	cout << ans << endl;

	return 0;

}