Codeforces Solution-A. Points in Segments-Solution in C, C++, Java, Python

Algorithm

You are given a set of $n$ segments on the axis $O x$ , 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 $l_{i}$ and $r_{i}$ ( $1 \leq l_{i} \leq r_{i} \leq 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 \leq x \leq r$ .

Input

The first line of the input contains two integers $n$ and $m$ ( $1 \leq n, m \leq 100$ ) — the number of segments and the upper bound for coordinates.

The next $n$ lines contain two integers each $l_{i}$ and $r_{i}$ ( $1 \leq l_{i} \leq r_{i} \leq m$ ) — the endpoints of the $i$ -th segment. Segments may intersect, overlap or even coincide with each other. Note, it is possible that $l_{i} = r_{i}$ , 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
Copy
3 5
2 2
1 2
5 5
output
Copy
2
3 4 
input
Copy
1 7
1 7
output
Copy
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.

Code Examples

#1 Code Example with C++ Programming

Code - C++ Programming

#include <bits/stdc++.h>

using namespace std;

int const N = 1e2 + 1;
int n, m, a[N], b[N];
vector<int> sol;

int main() {
  scanf("%d %d", &n, &m);
  for(int i = 0; i < n; ++i)
    scanf("%d %d", a + i, b + i);

  for(int i = 1; i <= m; ++i) {
    bool ok = true;
    for(int j = 0; j < n; ++j) {
      if(i >= a[j] && i <= b[j]) {
        ok = false;
        break;
      }
    }
    if(ok)
      sol.push_back(i);
  }

  printf("%d\n", int(sol.size()));
  for(int i = 0; i < sol.size(); ++i)
    printf("%d ", sol[i]);
  puts("");

  return 0;
}

Copy The Code & Try With Live Editor

Input

–

cmd

3 5
2 2
1 2
5 5

Output

–

cmd

2
3 4

Demonstration

Codeforces Solution-A. Points in Segments-Solution in C, C++, Java, Python,Points in Segments,Codeforces Solution

Previous
Codeforces solution 1080-B-B. Margarite and the best present codeforces solution

Next
CodeChef solution DETSCORE - Determine the Score CodeChef solution C,C+

Try With Live Editor

Category - Codeforces Online Judge Maniruzzaman Akash 1 year ago 642 0