Remove Interval
Practice
3 (4 votes)
Algorithms
Binary search
Problem
28% Success 833 Attempts 30 Points 1s Time Limit 256MB Memory 1024 KB Max Code
Given \(N\) intervals of the form \([L,R]\) .
Removal cost of an interval is defined as the number of intervals with which it overlaps other than itself.
Among the removal cost of all given intervals, find the minimum possible removal cost.
Input Format:
- First line contain \(N\), denoting the number of intervals
- Next \(N\) lines contain two integers \(L \ \ R\) , denoting the interval.
Output Format:
Print an integer corresponding to minimum removal cost among \(N\) intervals.
Constraints
\(1 \le N \le 10^5\)
\(1 \le L \le R \le 10^5\)
Explanation
Removal cost for interval 1 is 1 because it overlap with only interval 2.
Code Editor
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor
Results
Custom Input
Run your code to see the output
Submissions
Please login to view your submissions
Similar Problems
Points:30
53 votes
Tags:
Matrix ExponentiationMedium
Points:30
164 votes
Tags:
ApprovedBinary SearchMediumOpenSorting
Points:30
17 votes
Tags:
Binary SearchEasySorting
Editorial
Login to unlock the editorial
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor
Results
Custom Input
Run your code to see the output