Finding the total time elapsed in the union of time intervals

Question

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}};
answer(test) == 16
answer(test2) == 5

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

Here's my answer function:

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))
                t.add(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.

Answer 1

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;
        }
    }
    return totalTime;
}