(贪心) $O(nlogn)$
这道题也可以按左端点最小到大排序。
即排完序后的线段,在数组位置靠前线段左端点 < 数组位置靠后线段的左端点。
即对于每个线段$i$,要找到一个$j$使得,$L_i > R_j (loc_{last} + 1 <= j < i)$,所以我们搞个前缀$min$就行了。
注释:这里的$loc_{last}$指上一个选的线段的位置。
C++ 代码
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
typedef pair<int, int> PII;
const int N = 100005;
int n;
PII s[N];
int main(){
scanf("%d", &n);
for(int i = 1; i <= n; i++)
scanf("%d%d", &s[i].first, &s[i].second);
sort(s + 1, s + 1 + n);
int ans = 1, maxR = s[1].second;
for(int i = 2; i <= n; i++){
if(s[i].first <= maxR) maxR = min(maxR, s[i].second);
else ans++, maxR = s[i].second;
}
printf("%d\n", ans);
return 0;
}
maxR = min(maxR, s[i].second);这个处理我很喜欢,我学习啦,谢谢答主哦
为什么是min,不是max呢?
抱歉同学,我有点难解释,我的理解方法是在纸上画个线段,再分几种情况想象一下的
当进 if 的时候,说明当前枚举的区间和上一次最后的区间有交点 有交点的话我们选择右端点越靠左越有利(这样可以使得后面进if的可能小一些,对答案更有利~)~,(因为是左端点从小到大排序的)其实相当于用当前这个把上一次的区间替掉
请问sort是默认对左端点进行排序吗
应该是的,y总的代码对小于号进行了重置
才发现墨染空大佬用的是PII,y总用的是结构体
好的谢啦
pair自动根据first排序,结构体则需定义operator。
pair自动根据first排序,结构体则需定义operator。
这个代码也能过区间选点那道题,这是为什么?
你别说,我发现区间选点那个题目的代码放在这个题目也过了
大概是因为,每一个我们在第一题选取数字的那一部分上的几个区间里面选一个最优的,每个在第一题里面需要取数字的地方都取一个区间,最后选取的区间就是最多不重叠区间,那个答案就是第一问求的数
为什么要先设答案是1呢?
钦定了先有一段
醍醐灌顶
%%%
请问下这题我用区间选点的做法也可以ac,是不是这两种做法是一样的?
好吧,应该是的
是一样的,这个其实就是区间选点的本质做法
%%%
%%%%