Could you help with the task? He wrote his decision, but it is not true. Here is the challenge.

Input data

The first line contains the number N (1 <= N <= 100000) --- the number of segments. Further, the segments themselves are given in pairs of integers, the left and the right end. The coordinates of the ends lie in the range from 1 to 10 ^ 9.

Output

Print the number of segments in the desired set. Then output the segment in ascending order of the left end.

Example

Enter 3 10 12 1 5 3 7

Conclusion 2 3 7 10 12

Here is my decision. Yo it does not work. I cannot understand why the answer is 3 7 and 10 12, and not 2 (3 7) (10 12) and (1 5) (10 12).

#include "stdafx.h" #include <iostream> #include <windows.h> int n; int xy[100000][2]; int sum[100000][2]; int sum1[100000][2]; int nam; using namespace std; int main() { int j; nam = 0; cin >> n; for (int i = 0; i < n; i++) { cin >> xy[i][1] >> xy[i][2]; } for (j = 0; j < n; j++) { for (int b = j; b < n; b++) { if ((xy[j][1] < xy[b][1]) && (xy[j][2] < xy[b][1]) || xy[j][1] > xy[b][2]) { sum[j][1] = xy[j][1]; sum[j][2] = xy[j][2]; sum1[j][1] = xy[b][1]; sum1[j][2] = xy[b][2]; nam++; cout << sum[j][1] << " " << sum[j][2] << " " << endl << sum1[j][1] << " " << sum1[j][2] << endl; } } } cout << nam; }

Show plz on the example of code 2 day I can not write :(

  • (1 5) (10 12) will also be the correct answer. But still - 2 segments. - KoVadim
  • Well, because you need to find a subset (in theory, the answer (1 5) (10 12) also fits). The general idea of ​​the solution, it seems to me, will be the dynamics (it will first be necessary to sort only). - rasmisha
  • @Not even close, it seems that as a result of the edits, the goal (what should be done) Find the largest subset of> pairwise disjoint segments. disappeared from the question. - In general, I do not quite understand what “pairwise disjoint segments” means, the meaning is largely unclear in pairs . Apparently, therefore, I am also at a loss, why exactly (10 12) (3 7), and not (10 12) (1 5)? The only assumption is that 3 in (3 7) is greater than 1 in (1 5), and the condition states the order of withdrawal. Maybe this requirement should be extended to the choice of (1 5), (3 7) in a pair of (10 12) ??? - avp

1 answer 1

So you need to find non-intersecting segments. Actually, therefore, the answer is 2.