Boj 10165) 버스노선

문제

백준 10165

시간 복잡도

O(\(\mathrm{N}\log{\mathrm{N}}\))

코드

struct Edge {
	int s, e, idx; 
	bool operator<(Edge& in) { return s != in.s ? s < in.s : e > in.e; }
};
vector<Edge> arr;
bool masks[500001];

int main()
{
	fastio;

	int n, m; cin >> n >> m;
	for (int i = 1; i <= m; i++)
	{
		int a, b; cin >> a >> b;
		if (a > b) {
			arr.push_back(Edge{ a, b + n, i });
		}
		else {
			arr.push_back(Edge{ a, b, i });
			arr.push_back(Edge{ a + n, b + n, i });
		}
	}
	
	sort(arr.begin(), arr.end());
	int e = -1;
	for (auto& cur : arr)
	{
		if (cur.e <= e) masks[cur.idx] = 1;
		else e = cur.e;
	}
	for (int i = 1; i <= m; i++) if (!masks[i]) cout << i << ' ';
}