# Finding the total time elapsed in the union of time intervals

Given a set of time intervals, I have to find the total time elapsed in the union of the intervals.

Test Cases:

int[][] test = {{10, 14}, {4, 18}, {19, 20}, {19, 20}, {13, 20}};
int[][] test2 = {{1, 3}, {3, 6}};


Both of the tests pass, but I get a "time limit exceeded". How can I get this function to run faster?

public static int answer(int[][] intervals) {
ArrayList<Integer> t = new ArrayList<Integer>();
for (int i = 0; i < intervals.length; i++) {
for (int j = intervals[i][0]; j < intervals[i][1]; j++) {
if (!t.contains(j))
}
}
return t.size();
}


I also made an attempt without using the ArrayList and instead a regular array (int[]):

public static boolean wasWatched(int[] array, int time) {
for (int i = 0; i < array.length; i++) {
if (array[i] == time)
return true;
}
return false;
}
public static int[] addTimeWatched(int[] array, int time) {
int[] temp = new int[array.length + 1];
for (int i = 0; i < array.length; i++) {
temp[i] = array[i];
}
temp[array.length] = time;
return temp;
}


The answer() function was the same except t was an int[] and it used wasWatched(t, j) instead of t.contains(j) as well as t = addTimeWatched(t, j) instead of t.add(j).

Here is the full challenge text:

# Zombit monitoring

The first successfully created zombit specimen, Dolly the Zombit, needs constant monitoring, and Professor Boolean has tasked the minions with it. Any minion who monitors the zombit records the start and end times of their shifts. However, those minions, they are a bit disorganized: there may be times when multiple minions are monitoring the zombit, and times when there are none!

That's fine, Professor Boolean thinks, one can always hire more minions... Besides, Professor Boolean can at least figure out the total amount of time that Dolly the Zombit was monitored. He has entrusted you, another one of his trusty minions, to do just that. Are you up to the task?

Write a function answer(intervals) that takes a list of pairs [start, end] and returns the total amount of time that Dolly the Zombit was monitored by at least one minion. Each [start, end] pair represents the times when a minion started and finished monitoring the zombit. All values will be positive integers no greater than 2^30 - 1. You will always have end > start for each interval.

# Test cases

Inputs: (int) intervals = [[1, 3], [3, 6]] Output: (int) 5

Inputs: (int) intervals = [[10, 14], [4, 18], [19, 20], [19, 20], [13, 20]] Output: (int) 16

# Contraints

Your code will be compiled using standard Java 7. It must implement the answer() method in the solution stub.

Execution time is limited. Some classes are restricted (e.g. java.lang.ClassLoader). You will see a notice if you use a restricted class when you verify your solution.

Third-party libraries, input/output operations, spawning threads or processes and changes to the execution environment are not allowed.

• What exactly is the problem statement? Can't you just subtract the earliest start time from the latest end time? Commented Apr 28, 2016 at 0:25
• The problem states that sometimes there may be 2 people watching at the same time and at other times there will be 0 people watching at a time. I have to find the total time it was watched by at least 1 person. So if two people watch at the same time, that time only counts once (this is why I check if a certain time stamp already exists before adding it) Commented Apr 28, 2016 at 0:27
• What are the restrictions (number of intervals, total time range)?
– vnp
Commented Apr 28, 2016 at 2:36
• The only info I'm given on the input data is "All values will be positive integers no greater than 2^30 - 1. You will always have end > start for each interval." I don't know how many intervals there are Commented Apr 28, 2016 at 2:40
• Hi. Welcome to Code Review! Unless it's ridiculously long, I'd tend to post the entire thing here. Also, it would be helpful if you could post a problem statement and a link to the programming challenge. Commented Apr 28, 2016 at 3:08

You can make your current $O(n^2)$ algorithm run in $O(n \log n)$ time by first sorting the input intervals by interval start time, then do a linear scan of the sorted array:

public static int answer(int[][] intervals) {
if (intervals.length() < 1) {
return 0;
}
java.util.Arrays.sort(
intervals,
new java.util.Comparator<int[]>() {
public int compare(int[] a, int[] b) {
return Integer.compare(a[0], b[0]);
}
});
int totalTime = 0;
int currentIntervalEnd = intervals[0][0];
for (int[] interval : intervals) {
int intervalStart = interval[0];
int intervalEnd = interval[1];
if (intervalEnd > currentIntervalEnd) {
totalTime +=
intervalEnd - Math.max(intervalStart, currentIntervalEnd);
currentIntervalEnd = intervalEnd;
}
}