Jim and the Orders · Coding Gym

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<pair<int, int>> 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(' ')
)

Haskell

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

Multimap

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 <algorithm>
#include <iostream>
#include <map>

int main() {
  std::multimap<int, int> 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 << " ";
  }
}

patterns sort