Google Interview Question
Country: United States
Interview Type: In-Person
Hi Anant, I don't think greedy approach will work here. This question is bit different from interval scheduling. In interval scheduling once one event will get completed you can schedule any event which starts after the first will end. Here we are getting additional constraint that, next city should be reachable from current city in given time. For example suppose you are at city A, there are two city B and C which can be reached from A in given time, and both has festival on next week. Suppose festival in B falls before festival in C. In this case with greedy approach you will go to city B. But suppose there is some other city D which has festival in next week (one week later of B and C). Suppose D is reachable from C in one week time but not from B. In this case our selection C would have given better solution.
I think we need to explore all the possibility. It will be solved with DP.
3 words : Unweighted Interval Scheduling. The twist here is that you can only select an interval[j] after having selected interval[i] if it starts after interval[i].end + w[i][j] and is not in the same week as i. Here is the algorithm.
- anantpushkar009 November 14, 20141. Convert all time values to hour for consistency
2. Each site represents an interval. If not given in that format already, create an array containing start , end and index of site form which this interval was taken. Add an interval with start==end with index=start site.
3. Sort that array based on end time
4. Initialise count =0 and start with first interval and do the following till all intervals are exhausted:
4.1 Let i = current interval
4.2 Iteratively find the first j such that interval[j].start>=interval[i].end + w[i][j] and is not in the same week as i
4.3 i = j ; ++count
5. return count
Above is a greedy solution to Unweighted Interval Scheduling. To see the proof why it works: [www] .cse.psu.edu/~asmith/courses/cmpsc465/S12/lec-notes/CMPSC465-S12-Lec-17-greedy-algs.pptx.pdf , slide 9