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

Popular posts from this blog

Ansible - ERROR! the field 'hosts' is required but was not set -

customize file_field button ruby on rails -

SoapUI on windows 10 - high DPI/4K scaling issue -