I don't quite understand how am I going to implement and solve this problem:

Consider an array data of n numerical values in sorted order and a list of numerical target values (target values are not necessarily sorted). Your goal is to compute the smallest range of array indices that contains all of the target values. If a target value is smaller than data[0], the range should start with -1. If a target value is larger than data[n - 1], the range should end with n.

For example, given the array [ 5 8 10 13 15 20 22 26] and the target values (8, 2, 9, 17), the range is -1 to 5.

1. Devise an efficient algorithm that solves this problem and implement it in

   public static <T extends Comparable<? super T>>
   Interval findInterval(T[] sortedData, List<T> targetValues)
   

   Where Interval is a class that provides two public methods getLower() and getUpper() to return the lower and upper values of an Interval object. Implement the Interval class.

I understand the algorithm of the problem. However, I'm confused how I am going to to implement it. Like what would the return value be for the Interval findInterval method?

And "Implement the Interval class." I don't understand what exactly the getLower() and getUpper() methods are supposed to return or what type.

I hope someone can give me an idea how I am going to implement this.

CodePudding user response：

At first glance Interval should only be a data structure to hold the result of the calculation. Therefore, getLower & getUpper will not dynamically perform those calculations.

An example of such data structure may be:

public final class Interval {
   private final int lower;
   private final int upper;

   public Interval(int lower, int upper) {
       // Check preconditions, like lower can't be < -1, etc.
       this.lower = lower;
       this.upper = upper;
   }

   public int getLower() { return lower; }
   public int getUpper() { return upper; }
}

I think the most efficient algorithm would be O(log n m) assuming n sorted data and m target values.

1. First you must find the lowest & highest values in tagetValues. This can be done in O(m) by keeping a lowest & highest variables up to date while looping over all the elements.

2. Then you can do 2 subsequent binary searches on sortedData to find the lower index from the lowest and the highest index from the highest. This costs 2 log n which simplifies to O(log n).

Full implementation example:

import java.util.List;
import java.util.Arrays;

public class FindInterval {
  public static void main(String[] args) {
    Integer[] data = new Integer[] {5, 8, 10, 13, 15, 20, 22, 26};
    List<Integer> targets = Arrays.asList(8, 2, 9, 17);
    
    Interval interval = findInterval(data, targets);
    
    System.out.println(interval);
  }
  
  public static <T extends Comparable<? super T>> Interval findInterval(
    T[] sortedData, 
    List<T> targetValues
  ) {
    if (targetValues.isEmpty()) {
      throw new IllegalArgumentException("'targetValues' must not be empty.");
    }
    
    List<T> targetBounds = findTargetBounds(targetValues);

    int lower = Arrays.binarySearch(sortedData, targetBounds.get(0));    
    if (lower < 0 && lower != -1) {
      lower = Math.abs(lower) - 2;
    }
    
    int upper = Arrays.binarySearch(sortedData, targetBounds.get(1));
    if (upper < 0) {
      upper = Math.abs(upper) - 1;
    }
    
    return Interval.of(lower, upper);
  }
  
  private static <T extends Comparable<? super T>> List<T> findTargetBounds(List<T> targetValues) {
    T lower = targetValues.get(0);
    T upper = targetValues.get(0);
    
    for (T value : targetValues) {
      if (value.compareTo(lower) == -1) lower = value;
      if (value.compareTo(upper) == 1) upper = value;
    }
    
    return Arrays.asList(lower, upper);
  }
  
  private final static class Interval {
    private final int lower;
    private final int upper;
    
    private Interval(int lower, int upper) {
      // Check preconditions, like lower can't be < -1, etc.
      this.lower = lower;
      this.upper = upper;
    }
    
    public int getLower() { return lower; }
    public int getUpper() { return upper; }
    
    @Override
    public String toString() {
      return "["   lower   ","   upper   "]";
    }
    
    public static Interval of(int lower, int upper) {
      return new Interval(lower, upper);
    }
  }
    
}

CodePudding user response：

From what I can understand, getLower() is meant to return the lower range, and getUpper() is meant to return the higher range. So for the example given: getLower() -> -1 and getUpper() -> 5.

As for returning a class, you can simply do something like this in your method:

public static <T extends Comparable<? super T>>
Interval findInterval(T[] sortedData, List<T> targetValues) {
   ...
   return new Interval(...);
}

Does this answer your question?