重叠的装饰

#优化过的顺序dp插入判断方法，很好理解，百分百通过
def main():
    N = int(input())
    k = [[0, i, -1] for i in range(N*2)]
    maxs = 0
    i = 0
    while i < N*2:
        a, b = map(int, input().split())
        k[i][0] = a
        k[i+1][0] = b
        i += 2
#    print(k)
    k.sort(key=lambda x:x[0])
    k[0][2] = 0
    count = 0
    for i in range(1, len(k)):
        if k[i][2] == k[i-1][2]:
            k[i][2] = count
        else:
            count += 1
            k[i][2] = count
#    print("count", count)
    dp = [-1] * (count+1)
#    print(k)
    k.sort(key=lambda x:x[1])
#    print(k)
    i = 0
#    print(dp)
    while i < len(k):
        left = k[i][2]
        right = k[i+1][2]
        for j in range(left, right+1, 1):
            dp[j] = i
        i += 2
#    print(dp)
    dic = dict()
    for i in range(len(k)):
        dic[dp[i]] = dic.get(dp[i], 0)+1
#    print(dic)
    print(len(dic))
if __name__ == "__main__":
    main()

"""
一个实现起来很简单的思路，通过80%用例，考试时很实用，不知道改成C或java是不是还超时
对于示例1，所有左右边界组成的集合(1, 2, 3, 4, 6, 7, 8, 10)，分成七段；
借助字典从前到后为每一段赋值海报编号，
最后 每一段的值代表最上边可以看到的海报编号，
对字典的值求集合的长度，即为可见海报的张数
"""
import sys

if __name__ == "__main__":
    # sys.stdin = open("input.txt", "r")
    n = int(input().strip())
    a = []
    for _ in range(n):
        a.append(list(map(int, input().strip().split())))
    b = sorted(list(set(sum(a, []))))
    d = dict()
    for i in range(n):
        for j in range(b.index(a[i][0]), b.index(a[i][1])):
            d[str(b[j]) + '-' + str(b[j + 1])] = i
    ans = len(set(d.values()))
    print(ans)  

/*
对每一张海报t，
计算上一层海报未覆盖的(可见)区域(x,y)，
递归调用，直到t>n，海报t仍可以被看到，返回True；
或者直到某一层将可见区域完全覆盖，返回False。
by the way: 最后一个测试用例是错的吧，通过仔细对比已通过程序，26行改为27行通过全部用例 
*/
#include<bits/stdc++.h>
using namespace std;
#define N 10000
int n;
int a[N][2];

bool cover(int  x, int  y, int t)
{
    if (x >= y)
        return false;
    if (t >= n)
        return true;
    if (a[t][0] <= x && y <= a[t][1])
        return false;
    else if (a[t][0] >= y || a[t][1] <= x)
        return cover(x, y, t + 1);
    else if (x <= a[t][0] && a[t][1] <= y)
//        return cover(x, a[t][0], t + 1) || cover(a[t][1], y, t + 1)
        return cover(x, y, t + 1);
    else if (x < a[t][1] && a[t][1] < y)
        return cover( a[t][1], y, t + 1);
    else if (x < a[t][0] && a[t][0] < y)
        return cover( x, a[t][0], t + 1);
    return false;//所有情况都考虑到了，此句不需要；删除此句有时会编译不通过
}

int main()
{
//    freopen("input.txt", "r", stdin);
    cin >> n;
    for(int i = 0; i < n; i++) {
        cin >> a[i][0] >> a[i][1];
    }
    int ans = 0;
    for(int t = 0; t < n; t++)
        if(cover(a[t][0], a[t][1], t + 1))
            ans += 1;
    cout << ans << endl;
    return 0;
}