All Tracks Algorithms Greedy Algorithms Basics of Greedy Algorithms Problem

Little Monk and Library

Algorithms, Easy, Greedy algorithm


Little Monk as usual has not prepared for his exams. So, to ensure that he does not fail in any course, he goes to the library and picks up N books for his N courses that he has to give exams for. The number of books being too large, he puts them on different tables and goes to a particular table whenever he wants to read that particular book.

After he is done with studying, he has to put all the books back in their place. He finds that there are exactly N empty spaces in the book shelf where he can put his N books.

Imagine shelves and tables where books are kept, as locations on the x-coordinate axis. Now Little Monk wants to minimize the time he takes to put books back in shelves. He takes T units of time to put a book back in a shelf, where T denotes the distance between the book and the shelf it was put in.

Once Little Monk puts a book into a shelf, he takes 0 unit time to reach the next book he wants to put into a shelf. Since he is dumb, and in a hurry, help him calculate the minimum time required to put all the books in shelves.

Note: Once a book has been into a shelf, you can't put another book in the same shelf. Also, initially Monk can start from any book.

Input format:
The first line contains a pair of integers: an integer N, which denotes the number of books and empty shelves. Next line contains N space separated integers denoting co-ordinates of the tables where books are placed. Next line contains N space separated integers denoting co-ordinates of shelves.

Output format:
Print minimal time it will take Little Monk to put all books back in shelves.


2 1 3
4 3 2

Given co-ordinates of books and empty shelves, one of the possible combinations, where monk would incur minimal time is:

Book at co-ordinate 2 goes to shelf at co-ordinate 2.
Book at co-ordinate 1 goes to shelf at co-ordinate 3.
Book at co-ordinate 3 goes to shelf at co-ordinate 4.
Total time taken = 0 (2-2) + 2 (3-1) + 1 (4-3) = 3.

Time Limit: 0.5 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, TypeScript, Visual Basic


Initializing Code Editor...
Your Rating:


This Problem was Asked in


Challenge Name

CodeMonk (Greedy Technique)

View All Notifications