# Jim and the Orders

See the original problem on HackerRank.

## Solutions

This is a simple greedy algorithm.

Naming $$t_i$$ the time of order $$i$$ and $$d_i$$ the time needed to complete order $$i$$, we sort all the orders by $$t_i + d_i$$ and by $$i$$.

The idea implemented in C++:

  1 2 3 4 5 6 7 8 9 10  int N, ti, di; cin >> N; vector> orders(N); for (auto i=1; i<=N; ++i) { cin >> ti >> di; orders[i-1] = {ti+di, i}; } sort(begin(orders), end(orders)); for (const auto& o : orders) cout << o.second << " "; 

A Javascript solution by Simone Busoli:

 1 2 3 4 5 6 7 8  const orders = input.split('\n').slice(1).map(o => o.split(' ').map(Number).reduce((acc, c) => acc + c)) console.log( orders.map((t, i) => [t, i]) .sort(([t1, i1], [t2, i2]) => t1 - t2 || i1 - i2) .map(([, i]) => i+1) .join(' ') ) 

 1 2 3 4 5 6 7 8 9  import Data.List (sortOn) jimOrders :: [[Int]] -> [Int] jimOrders orders = fmap fst $sortOn snd$ zip [1..] $fmap (\[o,t] -> o+t) orders main = do c <- getContents let orders = fmap read . words <$> tail (lines c) putStr $unwords$ show <\$> jimOrders orders 
In C++ std::multimap is an associative sorted container. The elements are sorted by key. The same key can appear multiple times and when the same key is inserted, it is placed just after the other same key. Search, insertion, and removal operations have logarithmic complexity.
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19  #include #include #include int main() { std::multimap orders; int n; std::cin >> n; for (int i = 1; i <= n; ++i) { int orderNumber, prepTime; std::cin >> orderNumber >> prepTime; orders.insert(std::make_pair(orderNumber + prepTime, i)); } for (auto o : orders) { std::cout << o.second << " "; } }