We need to pre process this, Given the thread timings, we can create a int array of size max(endtimings) - min(start timings) and add 1 from array[start] to array[end] for each thread. Now, given a certain time, you can just lookup in the array, which takes O(1) time.

The above solution will work and will be efficient in terms of time. But the amount of storage required is going to be massive, especially since thread timings are going to be generally specified in precision of milliseconds and can potentially run for a long time. A more optimal solution in terms of space could be dividing the time between min(start) and max(end) in ranges and then store the corresponding threads for each range. Since a thread can cover a range fully or partially, we will need to store the start time and end time corresponding to each thread. The ranges can be decided based on the trade-off that is required between time and space efficiency. When size of ranges is 1, the solution will effectively turn into the one mentioned above.

I believe the best solution is as follows: You iterate through each thread and make note of where it starts and where it ends. You store this information in a sort of object that holds a time, the number of the thread, and whether or not the thread started or ended. Sort this list of objects based on time. You have essentially divided your space into time ranges based on the start/stop times of threads. Now we create some array of lists that has it's size set to the number of objects we created, BUT DO NOT fill this array with the objects! The array will be used to keep track of which threads are running in each time range. Iterate through the objects you made, filling up the lists in the array as you go. Example: Thread durations: 1: |---------| 2: |---| 3: |-------| Final array: {(1),(1,2),(1),(1,3),(3),null} Now you can do O(logn) lookup in the array with a basic binary search on the time ranges. The result in the array is what threads are running at that time.

Glassdoor formatted the picture so it is useless. Here is attempt 2: 1: |---------|......... 2: ... |---|............. 3: ............|-------|

@Jake The solution's pre-process can be faster. You can just store all times in an array, along with whether each time is a start/end time. The you can just traverse the array. This means that you don't need to figure out, for each discrete period in time, what threads are running. that could be pretty inefficient.

try using interval tree https://en.wikipedia.org/wiki/Interval_tree. You can then traverse the tree and find all timeranges that overlaps with given time t. The complexity is O(log n + m) where m is the number of results.

you might also divide overlaping timeranges into non-overlaping ranges. To each non-overlaping range assignlist of ranges that used overlaps there. Sample solution is here: http://stackoverflow.com/questions/628837/how-to-divide-a-set-of-overlapping-ranges-into-non-overlapping-ranges Then you can lookup the non-overlaping range that overlaps your given time t. Return list of ranges that used to overlaps there. You can do this with binary search (log n).