Company: Visa_29Aug
Difficulty: medium
Maximize Minimum Hotspot Distance The city council is installing free Wi-Fi hotspots along the main boulevard. The boulevard is a number line, and the council has marked n installation zones. The i -th zone is the closed interval [a_i, b_i] , and exactly one hotspot must be installed inside it, at an integer position x_i with a_i <= x_i <= b_i . To keep the signals from interfering, the council wants the hotspots spread out: the quality of a plan is the smallest distance |x_i - x_j| over all pairs of distinct hotspots i and j . Choose the positions so that this smallest distance is as large as possible, and report that value. Two hotspots may end up at the very same point; the smallest distance is then 0 . The zones are handed to you in no particular order, but they are guaranteed to be non-nested : no zone lies strictly inside another one. Formally, there is no pair of zones i and j with a_i < a_j and b_j < b_i . Input Format The first line contains an integer n , the numb