In a typical baton race (see picture) there are four runners and a single baton. Typically the baton is passed from one runner to the next until the race is complete. Here we will consider a modified baton race in which there are n runners and potentially more than one batons used, where runner i enters the race at point x; and exits at point y; (assume for simplicity that all these values are different and that the runners run in a straight line). Our race goes as follows: The first runner enters the race with his baton. In order to reduce the number of batons used, if runner i leaves at time y; and some other runner is in the race and follows, he will pass the baton to the other runner. Otherwise, he will leave the race with his baton, and the next runner to enter will have to bring a new baton. The race will continue like that until all runners finish. Given the entry-exit points (x1, y), (x2, y2), ...,(Xn, Yn), find the number of batons used overall. Give a O(n) algorithm for this problem. Give a better O(nlogn) algorithm for this problem. For each algorithm, argue about its correctness and running time