LearnToCP
Sign in
Navigation
HomeRoadmapProblemsAbout Us
Theory
Contest Knowledge
Selecting an IDEInteractive TasksOutput-Only Tasks
Basics
Your First ProgramData types and IOC++ syntaxModuloFunctionsVectorsMatricesTime Complexity
Sorting
SortingCounting sortRadix Sort
Optimization Techniques
Two PointersSum of numbers 1 to nPrefix sumBinary SearchGreedyBinary Search FunctionsBinary Search by AnswerDivide and Conquer
Binary Numbers
Binary NumbersNumbers in codeBitwise OperationsBitmasks
Math
Binary ExponentiationPrime NumbersPrime FactorizationGCD and LCMSieve of EratosthenesModified Sieve
Data Structures
StringsStackQueueMapsSetsPriority QueueCustom Criteria for FunctionsSegment TreesFenwick TreesSparse TablesUnion FindSqrt Decomposition
Combinatorics
Addition PrincipleMultiplication PrincipleCombinatoric ObjectsInclusion Exclusion Principle
Geometry
Geometry BasicsVectorsCross and Dot ProductLinesPolygonsAnglesPoint in PolygonDistances and Intersection PointsConvex HullCircles
Recursion
PointersRecursionGenerating Combinatoric Objects
Dynamic Programming
About DPDP problemsTree DPBitmask DPDigit DP
Graph Theory
GraphsDFS and BFSShortest PathsTreesTopological SortingDijkstra's AlgorithmMinimum Spanning TreesShortest Path Algorithms
Advanced Graph Theory
BiconnectivityStrongly Connected ComponentsBipartite GraphGraph FlowAugmenting PathsFlow - Minimum Cut DualityHeavy-Light DecompositionCentroid Decomposition
Advanced Data Structures
2D and 3D Segment TreesLazy PropagationImplicit Segment TreesPersistent Segment TreesLowest Common AncestorTrieBalanced Binary Search TreesMo's Algorithm

Movie Marathon

EasyProblem #9
Time LimitMemoryInputOutput
1 s64 MBstdinstdout

Think about which movie is the safest one to watch first.

A TV channel is airing a movie marathon tonight. The schedule lists n movies, and for each movie the time it starts and the time it ends. You want to watch as many movies as possible, but only whole movies - no skipping parts, no watching two at once.

The moment one movie ends, you are free to start another one (a movie that starts exactly when the previous one ends is fine).

Formally, given n intervals, find the largest number of them that can be chosen so that no two chosen intervals overlap.

Input

First line of input will be a single number n, the number of movies.
In the next n lines will be two numbers ai​ and bi​, the start and end time of each movie.

Output

A single number - the largest number of whole movies you can watch.

Example

Input
4
1 3
2 5
4 7
6 9
Output
2

You watch the movie 1→3, skip 2→5 (it already started while you were watching), watch 4→7, and skip 6→9. Two movies.

Constraints

1≤n≤2⋅105
0≤ai​<bi​≤109

Submit your solution

Sign in to submit your solution and track your progress.

Sign in to submit