C# · 12月 20, 2021

POJ1716(Integer Intervals)_NENUOJ(整数区间)_C++版@FDDLC

POJ1915:http://poj.org/problem?id=1716

NENUOJ:http://47.106.114.75/contest/24/problem/E

Description

An integer interval [a,b],a < b,is a set of all consecutive integers beginning with a and ending with b. 

Write a program that: finds the minimal number of elements in a set containing at least two different integers from each interval.

Input

The first line of the input contains the number of intervals n,1 <= n <= 10000. Each of the following n lines contains two integers a,b separated by a single space,0 <= a < b <= 10000. They are the beginning and the end of an interval.

Output

Output the minimal number of elements in a set containing at least two different integers from each interval.

Sample Input

4

3 6

2 4

0 2

4 7

Sample Output4 #include #include //用到了vector#include //用到了sortusing namespace std; //以上两个头文件都是C++特有的,而C没有struct node{int left,right;};bool ascending_order(node node_1,node node_2) //用于sort,按升序排列{return node_1.right < node_2.right;}int main(){int n; //行数scanf("%d",&n); //此行不能与下一行交换位置!!!vector node_vector(n); //n必须先输入再使用for(int index = 0; index < n; index++)scanf("%d%d",&node_vector[index].left,&node_vector[index].right);sort(node_vector.begin(),node_vector.end(),ascending_order); //排序,不能写成ascending_order()int former = node_vector[0].right – 1; //假如排完序后第一个区间为[3,6],则former = 5,latter = 6int latter = node_vector[0].right;int cnt = 2; //用于计数,当前已有两个数for(int index = 1; index = node_vector[index].left && former < node_vector[index].left) //一个在{former = latter;latter = node_vector[index].right;cnt++; //只增加了一个数}else if(latter < node_vector[index].left) //两个都不在{former = node_vector[index].right – 1;latter = node_vector[index].right;cnt += 2; //增加了两个数}}//两个都在时啥也不用干,故只考虑两种情况就行printf("%dn",cnt);return 0;}