Tahlil's blog

What is the solution of this problem ?
By Tahlil, 13 years ago, In English

You will be given several intervals. Every input of an interval consists of 3 numbers ai,bi,ci where a and b are the starting and ending of the interval. From all the intervals you have to find a set of integers Z which have ci number of common integers between ai and bi . You have to find out the minimum size of Z. 


Input:

6 8 3
8 10 3
1 3 1

output : 6


I saw this problem in many sites. But could not solve it. I tried but could not find any solution. Can anyone please explain how to solve this. Thanks very much :)


EDIT : The link of the problem is here http://acm.tju.edu.cn/toj/showp1664.html
  • Vote: I like it
  • -4
  • Vote: I do not like it

13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Nice problem!
I used following idea to solve this:
Intervals are like:[a,b,c]. Our resulting integer set-Z. Set of intervals-S.
While S is not empty{
  Choose the interval with minimum b value(ending of the interval).If there are several possible choices,choose any of them.Let denote this interval as I.In our resulting set Z,we must have at least c(I) numbers between a(I) and b(I).Let K denote the current count of numbers we already chose from a(I) to b(I).Then we must choose additional c(I)-K numbers from interval I.(If c(I)>K of course).Choose these numbers starting from right of the interval(iterate from right to left).If there is a number which we didn't use in our resulting set Z,add this number to the Z and continue until c(I)-K numbers added.Delete interval I and continue.
Adding from right of the interval is the key of the solution.Because we choose the interval I with minimum b time,other intervals in the set S\{b} have ending time>=b.
}
For above approach sorting of the intervals according to b value must be done.
After that , binary indexed tree can be used to check c(I)>K within one interval.
Of course,we must think additional quick operations to choose c(I)-K numbers from right side of the interval....
→ Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    I used your approach but instead of BIT I used binary search. But giving me WA :(
    → Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
you can use the system of system of difference constraints to solve it. 
→ Reply