Problem: Measuring Traffic
I can’t understand the second line of the sample output for this problem, which is “8 12”.
The range of values for the highway before the off-ramp is [11, 14] and the off-ramp outputs the range [2, 3]. So, a minimum of 2 units and a maximum of 3 units could exit the highway. If 2 (minimum) units exit the highway, the range of traffic after the N miles would be [11-2, 14-2] = [9, 12]. If 3 (maximum) units exit the highway, the range of traffic would be [11-3, 14-3] = [8, 11].
Now to find the intersection of these intervals. I’m pretty sure that the intersection of two intervals [a1, a2] and [b1, b2] is [max(a1,b1), min(a2,b2)], which would be [max(8,9), min(11,12)] = [9,11], but the sample output is actually [8,12] and I’m not quite sure why.
Thanks!
Well what it means by most specific range is the range s.t. only the values in the range are possible, i.e., for second line of sample, any value outside [8, 12] is impossible (but note both end-points are possible because simply 11 - 3 = 8 and 15 - 3 = 12). Therefore it is not about intersection of the two intervals you suggest, or else you are missing some possible values.
Okay, I think I have an idea on how to approach this problem now. Thanks for the help!