Tasks:
 
Task DescriptionDiscussion (0)
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 li and ri (-10000< li < di <10000) which represent the left and right ends of the interval (1<=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:
4
-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
UserTime
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