3
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ What exactly is the problem statement? Can't you just subtract the earliest start time from the latest end time? \$\endgroup\$ – 200_success Apr 28 '16 at 0:25
  • \$\begingroup\$ 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) \$\endgroup\$ – Ali Hamze Apr 28 '16 at 0:27
  • \$\begingroup\$ What are the restrictions (number of intervals, total time range)? \$\endgroup\$ – vnp Apr 28 '16 at 2:36
  • \$\begingroup\$ 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 \$\endgroup\$ – Ali Hamze Apr 28 '16 at 2:40
  • \$\begingroup\$ 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. \$\endgroup\$ – mdfst13 Apr 28 '16 at 3:08
4
\$\begingroup\$

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;
}
\$\endgroup\$
  • \$\begingroup\$ While this passes the tests, I don't want to submit it before understanding why it works better. What I understood from looking up the O Notation you used is that since I was running multiple operations on each interval (one outer loop going through the intervals and one inner loop going through each number in it) as opposed to yours where you just check one interval isn't within the next one before adding it that I was running extra unnecessary operations increasing the load time. \$\endgroup\$ – Ali Hamze Apr 28 '16 at 16:24
  • \$\begingroup\$ That's sort of the idea, yes. By using a more efficient algorithm you can tackle larger problems, which became prohibitively slow with more naive approaches like yours. \$\endgroup\$ – Jaime Apr 29 '16 at 7:04
  • \$\begingroup\$ @Jaime, I am thinking about extracting a subproblem first, merge overlapped intervals first, then adding total time will be easy to follow. \$\endgroup\$ – Jianmin Chen Jan 23 '17 at 4:09
  • \$\begingroup\$ @Jaime, here is the post about Leetcode 56: merge intervals, codereview.stackexchange.com/questions/153355/…; The algorithm also can derive an answer of total time through merged intervals easily. \$\endgroup\$ – Jianmin Chen Jan 23 '17 at 5:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.