Task DescriptionDiscussion (0)

The first line of the standard input contains a number

To the standard output in one line write the number of intervals which can be chosen so that they do not intersect.

Task :: intervali

You are given

**N**open intervals on a line (the intervals do not include their endpoints). Your task is to write a program which finds the largest number of intervals that can be chosen so they don't intersect.**INPUT:**

The first line of the standard input contains a number

**N**(0<

**N**<=5000), the number of intervals. The next

**N**lines contain two integers

**l**and

_{i}**r**(-10000<

_{i}**l**<

_{i}**d**<10000) which represent the left and right ends of the interval (1<=i<=

_{i}**N**).

**OUTPUT:**

To the standard output in one line write the number of intervals which can be chosen so that they do not intersect.

Input:

Output:

Explanation: The first, third, and fourth intervals don't intersect.

**4**

-1 1

0 5

2 3

5 9

-1 1

0 5

2 3

5 9

Output:

**3**

Explanation: The first, third, and fourth intervals don't intersect.

Submit Solution

Available Languages

Task info

Name: | intervali |

Time: | 0.05 sec. |

Memory: | 1 MB |

#Tests: | 10 |

AddedBy: | admin |

Task Ratings

Difficulty: | 3.8 (21 votes) |

Quality: | 4.1 (17 votes) |

Acceptance Rate

Recent Submissions

Fastest Solutions

User | Time |
---|---|

doctore | 0.006 s. |

bl4ck.c0d3r | 0.01 s. |

Ivan95 | 0.011 s. |

joooifications | 0.011 s. |

jovancina | 0.012 s. |

stratincica | 0.012 s. |

pgombar | 0.012 s. |

thewolf | 0.012 s. |

fushar | 0.012 s. |

syntax_error | 0.012 s. |

Solved By