区间相交

题面

给定 x 轴上 n 个闭区间。去掉尽可能少的闭区间，使剩下的闭区间都不相交。 给定 n 个闭区间，计算去掉的最少闭区间数。
输入数据的第一行是正整数 n (n <= 100)，表示闭区间数。接下来的 n 行中，每行有 2 个整数，分别表示闭区间的 2 个数端点。

输入输出

3
10 20
10 15
20 15

2

思路

见代码

代码

#include<iostream>
#include<cstring>
#include<string>
#include<cstdio>
#include<algorithm>
#include<vector>

const int N = 6;

using namespace std;

int n;

struct node {
	int l, r;
	int num;
	int i;
}a[N];

int e[N], ne[N], h[N], idx;
bool t[N],st[N][N];

void add(int a, int b)
{
	e[idx] = b; 
	ne[idx] = h[a];
	h[a] = idx++;
}

bool cmp(node a, node b)
{
	return a.num > b.num;
}

bool f()
{
	for (int i = 0; i < n; i++)
	{
		if (t[i]) continue;
		for (int j = h[a[i].i]; j!=-1; j = ne[j])
		{
			if (t[e[j]])continue;
			return false;
		}
	}

	return true;
}

int main()
{
	cin >> n;

	memset(h, -1, sizeof(h));

	for (int i = 0; i < n; i++)
	{
		int x, y;
		cin >> x >> y;
		a[i].l = min(x, y);
		a[i].r = max(x, y);
		a[i].i = i;
	}

	int sum = 0;

	for (int i = 0; i < n; i++)
	{
		int z = 0;
		for (int j = 0; j < n; j++)
		{
			if (j == i)continue;
			if (!(a[j].r<a[i].l || a[j].l>a[i].r)) {
				add(i, j);
				a[i].num++;
			}
		}
	}

	sort(a, a + n, cmp);

	int ans = 0;

	if (f()) {
		cout << 0;
		return 0;
	}
	else
	{
		for (int i = 0; i < n; i++)
		{
			t[i] = true;
			ans++;
			if (f()) {
				break;
			}


		}
	}
	cout << ans;

	return 0;
}