NYOJ891 找點

原題鏈接

思路：將每個區間段按照右端點從小到大排序，count賦值為n，從第一個開始以右端點為基准判斷是否在接下來的區段中間，若在則--count。

#include 
#include 

struct Node{
	int x, y;
};

Node arr[101];

int cmp(const void *a, const void *b){
	return (*(Node *)a).y - (*(Node *)b).y;
}

int main(){
	int n, i, j, count;
	while(scanf("%d", &n) == 1){
		for(i = 0; i != n; ++i)
			scanf("%d%d", &arr[i].x, &arr[i].y);
		qsort(arr, n, sizeof(Node), cmp);
		
		for(i = 0, count = n; i != n; ++i){
			for(j = i + 1; j < n; ++j)
				if(arr[i].y <= arr[j].y && arr[i].y >= arr[j].x)
					--count;
				else{
					i = j - 1;
					break;	
				}			
			if(j == n) break;
		}
		printf("%d\n", count);
	}
	return 0;
}