题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=4343
题目大意:给定N(N<=100000)个区间(左闭右开)和M(M<=100000)个询问[l, r],问所有满足[s,t)包含于于[l, r]的区间中最多能选出多少个,使得他们两两不相交。
解题思路:首先将坐标离散化,将区间排序后删掉可以覆盖其他区间的大区间。
这时若将剩余区间的左端点坐标排序,左端点坐标必然严格上升且对应的右端点坐标也是严格上升的。
此题的贪心思想较为普及,即按y的升序进行贪心固定区间询问的最大数量,不再赘述。
设g[1][x]为从坐标x开始向右遇到的第一个有效......
阅读全文