题目来源:https://codeforces.com/problemset/problem/1015/A
You are given a set of n segments on the axis Ox, each segment has integer endpoints between 1 and m inclusive. Segments may intersect, overlap or even coincide with each other. Each segment is characterized by two integers li and ri (1≤li≤ri≤m) — coordinates of the left and of the right endpoints.
Consider all integer points between 1 and m inclusive. Your task is to print all such points that don’t belong to any segment. The point x belongs to the segment [l;r] if and only if l≤x≤r.
Input
The first line of the input contains two integers n and m (1≤n,m≤100) — the number of segments and the upper bound for coordinates.
The next n lines contain two integers each li and ri (1≤li≤ri≤m) — the endpoints of the i-th segment. Segments may intersect, overlap or even coincide with each other. Note, it is possible that li=ri, i.e. a segment can degenerate to a point.
Output
In the first line print one integer k — the number of points that don’t belong to any segment.
In the second line print exactly k integers in any order — the points that don’t belong to any segment. All points you print should be distinct.
If there are no such points at all, print a single integer 0 in the first line and either leave the second line empty or do not print it at all.
Examples
Input
3 5
2 2
1 2
5 5
Output
2
3 4
Input
1 7
1 7
Output
0
Note
In the first example the point 1 belongs to the second segment, the point 2 belongs to the first and the second segments and the point 5 belongs to the third segment. The points 3 and 4 do not belong to any segment.
In the second example all the points from 1 to 7 belong to the first segment.
在轴Ox上给出一组n个段,每个段具有介于1和m之间的整数端点。段可以相互交叉,重叠或甚至重合。每个段的特征在于两个整数li和ri(1≤li≤ri≤m) - 左端点和右端点的坐标。
考虑1到m之间的所有整数点。您的任务是打印所有不属于任何细分的点。当且仅当l≤x≤r时,点x属于段[l; r]。
输入
输入的第一行包含两个整数n和m(1≤n,m≤100) - 段的数量和坐标的上限。
接下来的n行包含两个整数,每个li和ri(1≤li≤ri≤m) - 第i个分段的端点。段可以相互交叉,重叠或甚至重合。注意,有可能li = ri,即一个段可以退化到一个点。
产量
在第一行中打印一个整数k - 不属于任何段的点数。
在第二行中,以任何顺序精确打印k个整数 - 不属于任何段的点。您打印的所有点都应该是不同的。
如果根本没有这样的点,则在第一行中打印一个整数0,并将第二行留空或根本不打印。
注意
在第一示例中,点1属于第二段,点2属于第一段和第二段,点5属于第三段。第3点和第4点不属于任何细分。
在第二个示例中,从1到7的所有点都属于第一个段。
题意:给你一组n个段,每个段左右坐标给出,让你找出不属于如何段的点;
解题思路:将输入的每一个段包含的点都标记为1,就可以找出不属于所有线段的点了;其实数据比较小直接搜就可以过;
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <string.h>
using namespace std;
int main()
{
int a,b,n,m,sum=0;
cin>>a>>b;
int s[1500];
memset(s,0,sizeof(s));
for(int i=0;i<a;i++)
{
scanf("%d%d",&n,&m);
for(int i=n;i<=m;i++)//输入一组就标记一组;
{
s[i]=1;
}
}
for(int i=1;i<=b;i++)//它是从1,开始到b结束;
{
if(s[i]==1)//标记过就计算它标记的点;
{
sum++;
}
}
if(sum==b)
{
printf("0");
}
else//按格式打印;
{
printf("%d\n",b-sum);
for(int i=1;i<=b;i++)
{
if(s[i]==0&&i<b)
printf("%d ",i);
if(s[i]==0&&i==b)
printf("%d",i);
}
}
return 0;
}