Java find minimum range

Question

Question Description:

Given a list of companies, eg {ABC, BBC} and a large list of data looks like below:

Timestamp Security
10000000 IBM
10000001 Apple
10000005 PEAR
10000008 ABC
10000012 BBC

Find minimum time range where you can find all companies from list above.

My solution works and is brute force. But it has 3 loops. Can someone point out some ways to improve this solution in terms of runtime?

import java.util.*;
public class MinimumTimeRange {
 public static int findMinimumTimeRange(String [] list, String [] input){
 int n = list.length;
 Set<String> mySet = new HashSet<String>(Arrays.asList(list));
 int result = Integer.MAX_VALUE;
 for(int i=0; i<=(input.length-n);i++){
 for(int idx =n; idx<=(input.length-i);idx++){
 int [] timeList = new int [idx];
 Set<String> compSet = new HashSet<String>();
 for(int j=0;j<idx;j++){
 String[] tokens = input[i+j].split(" ");
 String time = tokens[0];
 String comp = tokens[1];
 timeList[j]=Integer.parseInt(time);
 compSet.add(comp);
 }
 if(compSet.containsAll(mySet)&& (timeList[idx-1]-timeList[0])<result){
 result = timeList[idx-1]-timeList[0];
 }
 }
 }
 return result;
 }
 public static void main(String[] args){
 String [] listCompanies = {"IBM","GE","GOOGLE"};
 String [] input = {
 "10000000 IBM",
 "10000001 Apple",
 "10000005 GOOGLE",
 "10000012 IBM",
 "10000013 TEST",
 "10000014 GE"
 };
 System.out.println(findMinimumTimeRange(listCompanies, input));
 }
}

Above code output 9, which is correct.

Other test examples:

String [] listCompanies = {"ABC","APPLE"};
String [] input = {
 "1 ABC",
 "2 TEST",
 "3 APPLE",
 "4 BBC",
 "12 APPLE",
 "13 ABC"
 };

Output: 1

• Sometowngeek: Are you trying to build the sorting algorithm yourself, or are you looking for a quick way to sort it?
• Angela P: hi, it's not a sort. the first column is Time, so it's trying to search for a range of time that those string in listCompanies appeared.
• Panayiotis Poularakis: So the input is always expected to be sorted in time?
• Angela P: @PanayiotisPoularakis yes

Answer 1

This can be reduced to a common problem : smallest range containing elements from k lists.

Assuming \$N\$ is the number of inputs and \$M\$ the number of companies in listCompanies.

In your problem, what you would do is make a set from your listCompanies (\$M \log M\$). Make a map where the keys are those companies and the values are lists (\$M \log M\$). Then, loop your input and if it's a company of interest (it has a key on the map), add that time to the list of that company.

So in your first example, IBM would be [10000000, 10000012]. After you have done this, you have now the common problem of finding the minimum range in which you can have one item from each of those lists (minimum range that has each of your companies in listCompanies).

You can then apply the algorithm linked and end up with a complexity of (\$N \log M\$ -> each element will enter and leave a heap of size \$M\$ only once). \$N\$ in this case will be the amount of inputs that are related to companies from your listCompanies.

Here is a C++ implementation.