We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  • Hackerrank Home
  • Prepare
    NEW
  • Certify
  • Compete
  • Career Fair
  • Hiring developers?
  1. Prepare
  2. Algorithms
  3. Dynamic Programming
  4. Interval Selection

Interval Selection

Problem
Submissions
Leaderboard
Discussions
Editorial

Given a set of intervals, find the size of its largest possible subset of intervals such that no three intervals in the subset share a common point.

Input Format

The first line contains an integer, , denoting the number of interval sets you must find answers for. The subsequent lines describe each of the interval sets as follows:

  1. The first line contains an integer, , denoting the number of intervals in the list.
  2. Each line of the subsequent lines contains two space-separated integers describing the respective starting () and ending () boundaries of an interval.

Constraints

Output Format

For each of the interval sets, print an integer denoting the size of the largest possible subset of intervals in the given set such that no three points in the subset overlap.

Sample Input

4
3
1 2
2 3
2 4
3
1 5
1 5
1 5
4
1 10
1 3
4 6
7 10
4
1 10
1 3
3 6
7 10

Sample Output

2
2
4
3

Explanation

For set , all three intervals fall on point so we can only choose any of the intervals. Thus, we print on a new line.

For set , all three intervals span the range from to so we can only choose any of them. Thus, we print on a new line.

For set , we can choose all intervals without having more than two of them overlap at any given point. Thus, we print on a new line.

For set , the intervals , , and all overlap at point , so we must only choose of these intervals to combine with the last interval, , for a total of qualifying intervals. Thus, we print on a new line.

Author

HackerRank

Difficulty

Medium

Max Score

65

Submitted By

2213

Need Help?


View discussions
View editorial
View top submissions

rate this challenge

MORE DETAILS

Download problem statement
Download sample test cases
Suggest Edits
  • Contest Calendar
  • Blog
  • Scoring
  • Environment
  • FAQ
  • About Us
  • Support
  • Careers
  • Terms Of Service
  • Privacy Policy
  • Request a Feature