You are a farmer living in a 2-dimensional world. Your crops look like an infinite line parallel to the x-axis, with the y-coordinate equal to 0. According to the weather forecast, the next rain will be acid, and therefore very harmful to your plants. The rain consists of an infinite number of drops that fall down vertically (parallel to the y-axis). For every x, where x is an arbitrary number (not necessarily an integer), a drop will fall toward the point (x, 0).
To protect your crops, you have built some shields above the ground. Each shield is a line segment parallel to the x-axis, with negligible thickness. If a drop of rain falls on a shield, it will flow to the closest end of the shield and continue falling straight down vertically from that point. If a drop falls exactly in the middle of a shield, the drop will divide into two equal parts that flow to opposite ends of the shield and continue falling from there. If two or more shields have common endpoints they will act as one combined shield. See examples for clarification.
The locations of your existing shields will be given in the three int[]s b, e and y. The endpoints of the i-th shield are located at (b[i], y[i]) and (e[i], y[i]). Define B as the minimum value in b, and E as the maximum value in e. Your task is to build enough additional shields to protect all the crops between (B, 0) and (E, 0), exclusive (that is, all crops whose x-coordinates lie in the open interval (B, E) ). Each shield must be a line segment parallel to the x-axis with non-zero length and a positive y-coordinate. Each shield you build must have integer endpoints and a positive length. Build these new shields in such a way that the sum of their lengths is minimized. Return the sum of the new shields' lengths.
|