hi, I’m trying to solve this problem, any hint will be appreciated.
There are some horizontal segments in the axis. We want to remove minimum number of segments in order to any vertical line can cross at most t of them ,where t<=K. Given n segment and their descriptions (y x1 x2) and K. solve this problem with a good time order.
This isn’t a Programming Contest problem, so there is no explicit range for n and x1 x2 y.
http://acm.tju.edu.cn/acm/showp1264.html
simplified version of this problem?
there're O(n) greedy algorithm.
thanks for your link and hint, but i cant solve this by an O(n) solution, can you explain more ?
are all segments have 1 unit of thickness?
in my problem yes , but in the problem you linked,it seems vertical segment exist too. would you please explain your solution for problem on tju ?
Could you please explain your approach ?
Please anyone give me some hints for solving this problem or send me his code. Thanks.
Are x1,x2 integers ?
Yes
Take the leftmost end of an interval. Count all intervals that cover that point (start before it); if there are more than K, remove the ones with rightmost ends so that there'd be K left. Ignore the interval that had the leftmost end and repeat. This is a basis for a greedy algorithm — sort the intervals by their ends, then move a sweepline along their ends from left to right; if you have more than K intervals covering some end, remove the ones with rightmost ends. We can update the
.
set<>of opened intervals quickly and only remove each interval once, so the time complexity isgot it. Thanks a lot :)