GayHawk's blog

Need a bit of help with DS
By GayHawk, 6 years ago, In English

You are given N segments defined by their starting point ai and end point bi. You need to determine the number of points such that at least K segments contain them.
What is the most efficient way to do this task? Thanks in advance.

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

Comments Comments (2)
| Write comment?
»
6 years ago, # |
  Vote: I like it +9 Vote: I do not like it

You need to take a look this problem on codeforces .

I am sure this will help you.

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

Well there was a task on Codeforces similar to this, but I will describe the idea here: save a vector of points. Starting points are type 1, ending points are type 0. Save into the vector a pair, <position, type>. Now sort the vector based on the positions, and also keep track of the current number of segments. Here the task is now pretty simple, just check our current count with K and add to answer the appropriate values

→ Reply