Food Chain
Time limit1sMemory limit256 MB
Given N intervals, find the longest chain where each interval strictly contains the next (with ties allowed on one endpoint), essentially a longest chain problem solvable via sorting and LIS-style binary search.
- Level
Medium6 of 10
- Topics
- Binary search, Sorting, Dynamic programming
- Solved
- No attempts yet
Problem
There are N distinct animals numbered from 1 to N. Each animal is active on one continuous interval of the same horizontal line. This interval is called the animal's activity range.
For animal i with activity range (x1, x2) and animal j with activity range (x3, x4), animal i is above animal j in the food chain if one of the following holds.
- x1 < x3 and x2 > x4
- x1 = x3 and x2 > x4
- x1 < x3 and x2 = x4
In other words, animal i's activity range contains animal j's activity range, and the two ranges are not exactly identical.
A group of animals has a food-chain structure if its animals can be listed in one row so that every animal in the row is above every animal that appears after it. A group containing a single animal also has a food-chain structure. The size of a group is the number of animals in it.
Given every animal's activity range, find the largest possible size of a group that has a food-chain structure.
Input
The first line contains the number of animals N (1 ≤ N ≤ 500,000).
Each of the next N lines contains an animal number, the left position L of its activity range, and the right position R of its activity range, separated by spaces. L and R are positive integers between 1 and 1,000,000,000 inclusive. The animal number identifies the input row; the answer is determined by the activity ranges.
Output
Print the maximum size of a group that has a food-chain structure.