A number of points along the highway are in need of repair. An equal number of crews are available, stationed at various points along the highway. They must move along the highway to reach an assigned point. Given that one crew must be assigned to each job, what is the minimum total amount of distance traveled by all crews before they can begin work?
For example, given crews at points {1,3,5} and required repairs at {3,5,7}, one possible minimum assignment would be {1→ 3, 3 → 5, 5 → 7} for a total of 6 units traveled.
Function Description
Complete the function getMinCost in the editor below. The function should return the minimum possible total distance traveled as an integer.
getMinCost has the following parameter(s):
crewId[crewId[0],...crewId[n-1]] : a vector of integers
jobId[jobId[0],...jobId[n-1]] : a vector of integers
Constraints
- 1 < n < 105
- crewId[i] : 1 < crewId[i] < 109
- jobId[i] : 1 < jobId[i] < 109
Input Format For Custom TestingThe first line contains an integer, n, denoting the number of elements in crew_id and job_id.
Each line i of the n subsequent lines (where 0 < i < n) contains an integer describing crew_id[i].
The next line again contains the integer n as above.
Each line i of the n subsequent lines (where 0 < i < n) contains an integer describing job_id[i].
Sample Input For Custom Testing
5
5
3
1
4
6
5
9
8
3
15
1
Sample Output
17
Explanation
By index, crewId[i] → jobId[i], { (0 → 0) , (1 → 2) , (2 → 4) , (3 → 3) , (4 → 1) } is one possible assignment for a minimum cost of 17. Showing element values, this is { (5 → 9) , (3 → 3) , (1 → 1) , (4 → 15) , (6 → 8) } yielding a total travel distance of 4 + 0 + 0 + 11 + 2 = 17.
Sample Input For Custom Testing
4
5
1
4
2
4
4
7
9
10
Sample Output
18
Explanation
By index, { (1 → 0) , (0 → 1) , (2 → 2) , (3 → 3) } is one possible assignment for a minimum cost of 18.
Solution(Java):-
import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.function.*;
import java.util.regex.*;
import java.util.stream.*;
import static java.util.stream.Collectors.joining;
import static java.util.stream.Collectors.toList;
class Result {
/*
* Complete the 'getMinCost' function below.
*
* The function is expected to return a LONG_INTEGER.
* The function accepts following parameters:
* 1. INTEGER_ARRAY crew_id
* 2. INTEGER_ARRAY job_id
*/
public static long getMinCost(List<Integer> crew_id, List<Integer> job_id) {
// Write your code here
Collections.sort(crew_id);
Collections.sort(job_id);
long c=0;
for(int i=0;i<crew_id.size();i++)
{
c+=Math.abs(job_id.get(i)-crew_id.get(i));
}
return c;
}
}
public class Solution {
public static void main(String[] args) throws IOException {
BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));
int crew_idCount = Integer.parseInt(bufferedReader.readLine().trim());
List<Integer> crew_id = IntStream.range(0, crew_idCount).mapToObj(i -> {
try {
return bufferedReader.readLine().replaceAll("\\s+$", "");
} catch (IOException ex) {
throw new RuntimeException(ex);
}
})
.map(String::trim)
.map(Integer::parseInt)
.collect(toList());
int job_idCount = Integer.parseInt(bufferedReader.readLine().trim());
List<Integer> job_id = IntStream.range(0, job_idCount).mapToObj(i -> {
try {
return bufferedReader.readLine().replaceAll("\\s+$", "");
} catch (IOException ex) {
throw new RuntimeException(ex);
}
})
.map(String::trim)
.map(Integer::parseInt)
.collect(toList());
long result = Result.getMinCost(crew_id, job_id);
bufferedWriter.write(String.valueOf(result));
bufferedWriter.newLine();
bufferedReader.close();
bufferedWriter.close();
}
}
