题意：

第一问：n条线段，问最多选多少条线段不相互覆盖

第二问：输出满足第一问中字典序最小的方案

思路：

第一问非常显然，只需按照线段右端点排序，右端点越靠前越优，然后直接贪心就好。

第一问的贪心方法启示了我们，如果一定要选一条线段，他选的下一条线段一定是固定的（即左端点大于他右端点中右端点最小的线段）

那么第二问怎么做呢

我们可以这样想，按编号依次枚举每条线段是否可以放入，即可

做法：

1.如何判断是否可以放入？

一条线段能影响的范围一定只是之前放过的线段中间的区域，我们只要保证他自身的贡献加上他左侧能影响的区域和他右侧能影响的区域的贡献等于整个的他能影响的区域的贡献且不与之前已经放入的线段相交

2.如何计算一段区域的贡献？

因为如果一定要选一条线段，他选的下一条线段一定是固定的，所以我们可以预处理出每条线段的可以跳的下一个位置的st表就可以O(logn)查询

3.如何找他可以影响的区域？

可以用一个set维护，具体可以看代码

code:

#include <bits/stdc++.h>
using namespace std;

const int N = 2e5 + 10;

const int inf = 1e9;

struct www{
	int l, r, id;
}arr[N];

www ww(int l,int r,int id){
	www u; u.l = l; u.r = r; u.id = id; return u;
}

int tmp[N<<1], cnt;

int n, st[N][20], mn[N<<1], pos[N<<1];

struct node{
	int v, id;
	friend bool operator < (node a,node b){
		return a.v < b.v;
	}
};

set<node> s;

node nd(int v,int id){
	node u;u.v = v;u.id = id;return u;
}

int f(int cur,int r){
	int res = 0;
	for(int p = 18;p >= 0; p--){
		if(arr[st[cur][p]].r <= r){
			res += (1 << p);
			cur = st[cur][p];
		}
	}
	return res;
}
//读入和离散化 
void read(){
	cin >> n;
	for(int i = 1;i <= n; i++){
		int l, r;
		cin >> l >> r;
		tmp[i*2-1] = l;
		tmp[i*2] = r;
		arr[i] = ww(l,r,i);
	}
	sort(tmp+1,tmp+1+n*2);
	cnt = unique(tmp+1,tmp+1+n*2)-tmp-1;
	for(int i = 1;i <= n; i++){
		arr[i].l = lower_bound(tmp+1,tmp+1+cnt,arr[i].l) - tmp;
		arr[i].r = lower_bound(tmp+1,tmp+1+cnt,arr[i].r) - tmp;
	}
	return ;
}
//预处理st表 
void init(){
	sort(arr+1,arr+1+n,[](www a,www b){return a.l < b.l;});
	arr[n+1] = ww(inf,inf,n+1);
	arr[0] = ww(-inf,-inf,0);
	memset(mn,0x3f,sizeof mn);
	mn[cnt+1] = cnt+1;
	pos[cnt+1] = n+1;
	for(int i = n;i > 0; i--){
		if(mn[arr[i].l] > arr[i].r){
			mn[arr[i].l] = arr[i].r;
			pos[arr[i].l] = arr[i].id;
		}
	}
	for(int i = cnt;i > 0; i--){
		if(mn[i] > mn[i+1]){
			mn[i] = mn[i+1];
			pos[i] = pos[i+1];
		}
	}
	st[n+1][0] = n + 1;
	for(int i = 1;i <= n; i++){
		st[arr[i].id][0] = pos[arr[i].r+1];
	}
	int cur = n + 1;
	for(int i = 1;i <= n; i++){
		if(arr[i].r < arr[cur].r) cur = i;
	}
	st[0][0] = arr[cur].id;
	for(int p = 1;p <= 18; p++){
		for(int i = 0;i <= n + 1; i++){
			st[i][p] = st[st[i][p-1]][p-1];
		}
	}
	return ;
}
//求从第cur个线段到r的线段个数 
int get(int cur,int r){
	int res = 0;
	for(int p = 18;p >= 0; p--){
		if(arr[st[cur][p]].r <= r){
			cur = st[cur][p];
			res += (1 << p);
		}
	}
	return res;
}

void compute(){
	sort(arr+1,arr+1+n,[](www a,www b){return a.id < b.id;});
	int m = get(0,inf-1);
	cout << m << '\n';
	s.insert(nd(-inf,0));
	s.insert(nd(inf,n+1));
	set<node>::iterator it;
	for(int i = 1;i <= n; i++){
		if(s.upper_bound(nd(arr[i].l,i)) != s.upper_bound(nd(arr[i].r,i))) continue;//重合 
		it = s.upper_bound(nd(arr[i].r,i));
		node r = *it;
		it--;
		node l = *it;
		if(get(l.id,arr[i].l-1)+get(i,r.v-1)+1!=get(l.id,r.v-1)) continue;
		cout << i << ' ';
		s.insert(nd(arr[i].l,i));
		s.insert(nd(arr[i].r,i));
	}
	return ;
}

int main(){
	read();
	init();
	compute();
	return 0;
}