Electric Wires 2
Time limit1sMemory limit128 MB
Given N wires between two poles, remove the minimum number of wires so the rest form an increasing sequence (longest increasing subsequence based removal), listing the removed A-positions.
- Level
Medium6 of 10
- Topics
- Binary search, Sorting, Array
- Solved
- No attempts yet
Problem
Several electric wires connect utility poles A and B. If two different wires cross, there is a risk of a short circuit, so some wires must be removed so that no remaining wires cross.
In the configuration shown below, removing the wire connecting position 1 on pole A to position 8 on pole B, the wire connecting position 3 on pole A to position 9 on pole B, and the wire connecting position 4 on pole A to position 1 on pole B leaves all remaining wires non-crossing.
Positions where wires attach to a pole are numbered from top to bottom. Given the number of wires and the position numbers where each wire is attached to the two poles, find the minimum number of wires that must be removed to eliminate all crossings, and output the position numbers on pole A for the wires to remove.
Input
The first line contains the number N of wires between the two poles. N is a positive integer not greater than 100,000.
Each of the next N lines contains two integers: the position number where one wire is attached to pole A, followed by the position number where that wire is attached to pole B. Each position number is a positive integer not greater than 500,000. No two wires are attached to the same position on the same pole.
Output
On the first line, print the minimum number of wires that must be removed so that all remaining wires are non-crossing.
Starting on the second line, print the pole-A position number of each wire to remove, one per line, in increasing order. If there is more than one valid answer, print any one of them.