Lines at a Counter Algorithm.
A group of n people is waiting in line at a service center. They have been waiting for a long time since only one counter is open, and are very tired and in an irritated mood. Suddenly, the service center decides to close the rest counter and open a second counter instead. Everyone sees an opportunity to get served quickly and runs to the new counter. In the ensuing chaos, people change their positions in the line, and once the new line forms, loud arguments break out between pairs of individuals whose relative position in the line got ripped. (I.e., if person A was ahead of person B earlier, and now person B is ahead of person A, then they start quarreling.) To stop the arguments, the authorities want to expel a set of people from the new line and decide that the best strategy is to expel the maximum number of people every pair of whom is arguing with one another. Can you help the authorities identify such a group of people on time? (This problem can be solved faster, but requires a more complicated algorithm.)
Problem One Solution
First of all, let us enumerate people in the line according to their place and denote si — position of person I before the line changed. Now, if for 3 people i < j < k we have quarreling i with j and j with k that means si > sj and sj > sk respectively which leads to si > sk and i is also arguing with k. Our task is finding the longest sequence of i1, i2, . . . , im such that si1 > si2 > • • • > sim. An easy way of solving this in O(n 2 ) time is as follows: we start from the beginning and on step k we calculate f(k) — the longest such sequence ending with k — and g(k) — the predecessor of k in such sequence. This can be done in O(k) time by simply running through all previous values of f(1), . . . , f(k − 1) and taking a maximum of those that can be extended by k and assigning f(k) = max k extends i f(i) + 1 or simply 1 if none found and adjusting g(k) accordingly. By running this for all people in O(n 2 ) time we take a maximum of all f(i) values and by running from its end and taking g(previous person) we get the required group in O(n) additional time resulting in O(n 2 ) overall.
Book bagging for Courses Algorithm
You are book bagging for courses in the next semester. There are n courses in total, and for every course, you have been given the number of hours (between 1 and 10) you will need to spend on the course every week and the number of credits (between 1 and 3) you will earn after taking the course (assume that both the number of hours spent per week and credit earned are integers for every course). In addition, for every course, you have calculated a number that represents how much you will learn in the course based on previous courses you have taken and the experience shared by your peers (let us call this number \learning" in the course for you).
Problem 2 solution
Assuming that constants 10, 3, and 40 are relatively small compared to n we can do it in O(n) time. We calculate f(n) — best value of courses you could get for n hours (best credits and from all with the same credit total best in learning value) and the courses for that value. We run from m = 0 to m = 40 on each step finding maximum value among the following: best f(m−1) value + best value ≤ 1-hour course remaining, best f(m−2) value + best value ≤ 2-hour course remaining, ..., best f(m−10) value + best value ≤ 10-hour course remaining. For maximum, we assign the best fitting course as the best solution accompanying f(m). All these bests are computed in O(n) time (simple 2-level maximal with constant condition checking). Overall time for f(i) calculation is O(n) and we need to do this m = 40 times which gives us O(mn) = O(n) time.