Блог пользователя WorstCoder45

Автор WorstCoder45, история, 4 года назад, По-английски

This problem is from some old contest of codeforces , I don't remember its name anymore . But the problem idea seems interesting.

Problem :

Given $$$n$$$ segments $$$[l,r]$$$ , segment $$$[l1,r1]$$$ belongs to the first person, $$$[l2,r2]$$$ belongs to the second person, and so on...

Each person should select any one day/number from his own segment.

We have to find any assignment for every person to a particular day, such that every person has selected a unique day .

Example :

Range of first person : $$$[1,5]$$$

Range of second person : $$$[7,8]$$$

Solution : First person selects day-1 and second person selects day 7.

Another example :

Range of first person : $$$[1,2]$$$

Range of second person : $$$[1,3]$$$

Solution : First person selects day-1 and second person selects day 2.

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

If n is not very big you can try Kuhn algorithm.