algorithm - Given an array of ranges find the total distance covered? -
here interview question heard about. have range of arrays elements length 2 arrays starting point , end point on number line. there can overlaps. need return total distance covered. how solve this?
example: input: [[3,5], [1,3], [2,4]]
output: 4
my thoughts: you'd need keep track of ranges covered , if value in particular range. not sure how though?
here implementation.
since every range has min value , max value (|min|------|max|) if have sorted list, can find distance wasn't covered subtracting current min last max. if value negative, know no difference found between 2 ranges. don't have include range, store new maximum.
import java.util.arraylist; import java.util.hashmap; public class main { public static void main(string[] args) { //given sorted array index @ 0 // (equal array[0] sorted array[1]. //if array isn't sorted sort here arraylist<int[]> ranges = new arraylist<>(); ranges.add(new int[]{1,3}); ranges.add(new int[]{2,4}); ranges.add(new int[]{3,5}); //getsortedarray(ranges); //not implemented here int min = ranges.get(0)[0]; int totaldifference = 0; int lastmax = 0; int max = 0; for(int = 0; < ranges.size(); i++){ if(i == 0){ //the highest max current index @ 1 lastmax = ranges.get(i)[1]; }else{ int tempmin = ranges.get(i)[0]; int diff = (tempmin - lastmax); //only if range above last range. // negative means there no difference. if(diff > 0) { //subtract new min of range last max // gives distance between ranges. totaldifference += diff; } lastmax = ranges.get(i)[1]; // set new last max } max = ranges.get(i)[1]; } system.out.println("total distance = " + (max - min - totaldifference)); } }
Comments
Post a Comment