algorithm - Interview puzzle on traveling on a line segment -

algorithm - Interview puzzle on traveling on a line segment -

here's interesting question came upon:

let's on number line of length m, 0 < m <= 1,000,000,000, given n (1 < n <= 100,000) integer pairs of points. in each pair, first point represents object located, , sec point represents object should moved. (keep in mind second point may smaller first).

now, assume start @ point 0 , have cart can hold 1 object. want move objects initial positions respective final positions while traveling to the lowest degree distance along number line (not displacement). have end on point m.

now, i've been trying cut down problem simpler problem. honest can't think of brute forcefulness (possibly greedy) solution. however, first thought degenerate backwards motion 2 forwards movements, doesn't seem work in cases.

i drew out these 3 sample test cases in

the reply first testcase 12. first, pick red item @ point 0. move point 6 (distance = 6), drop red item temporarily, pick green item. move point 5 (distance = 1) , drop green item. move point 6 (distance = 1) , pick red item dropped, move point 9 (distance = 3), move point 10 (distance = 1) finish off sequence.

the total distance traveled 6 + 1 + 1 + 3 + 1 = 12, minimum possible distance.

the other 2 cases have answers of 12, believe. however, can't find general rule solve it.

anyone got ideas?

suppose given these moves (a, b), (c, d), (e, f), ... minimum distance have travel abs(b - a) + abs(d - c) + abs(f - e) + ... , actual distance travel abs(b - a) + abs(c - b) + abs(d - c) + abs(e - d) + .... basically, given array of moves point minimize "travel distance" function swapping elements around. if consider particular combination node , combinations can reach edges can utilize 1 of many graph search algorithms around create utilize of heuristic. 1 illustration beam search.

algorithm