sam
BAN USERTwo comments:
1) It is only for one array and not two.
2) It is not O(n), since you still need to find two farthest index which have same value. You cannot just check the value at starting index with the rest of the array.
For example if array is: 1 1 1 1 1 0 0 1 1 1 1 1.
Temp array: 1 2 3 4 5 4 3 4 5 6 7 8. Actual answer would be : m = 3rd index + 1, n = 7th index. In fact there are multiple answers, I am just searching for values from the starting. So complexity is actually: O(n*n) in worst case.
Just a try:
Sort the jobs by max_waiting_time.
Step 1: For each job, find the taxi at the nearest location(s) and assign it for the job if it can reach within the waiting time. This way we are minimizing both the unsatisfied and non-revenue distance.
Step 2: However, we also need to take care that what happens when a taxi has completed current job. I would update each location with those taxis as well which have their destination set to that location and have additional wait time for that taxi, equal to the time for current job
and repeat step 1.
Please let me know your views
To make it O(n), one suggested method is to take a hash table and start saving the index of the values from temp array. If the value repeats, find the diff with existing index and if the difference is greater than maxdiff then update it.
- sam August 28, 2013