MehrdadAP's blog

Any hint for this problem
By MehrdadAP, 11 years ago, In English

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.

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

http://acm.tju.edu.cn/acm/showp1264.html

simplified version of this problem?

there're O(n) greedy algorithm.

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    thanks for your link and hint, but i cant solve this by an O(n) solution, can you explain more ?

    → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      are all segments have 1 unit of thickness?

      → Reply
      • »
        »
        »
        »
        11 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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 ?

        → Reply
      • »
        »
        »
        »
        11 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Could you please explain your approach ?

        → Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Please anyone give me some hints for solving this problem or send me his code. Thanks.

→ Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Are x1,x2 integers ?

→ Reply
»
11 years ago, # |
  Vote: I like it +7 Vote: I do not like it

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 is .

→ Reply