CtCI - Overlapping Ranges

CtCI - Overlapping Ranges

Given a list of objects containing the login and logout times for multiple users, determine what is the maximum number of concurrent users logged in at the same time.

[
  {user: A, login: 1, logout: 3},
  {user: B, login: 3, logout: 4},
  {user: C, login: 1, logout: 2},
  {user: D, login: 20, logout: 30},
  {user: E, login: 1, logout: 3},
  {user: F, login: 4, logout: 8},
  {user: G, login: 5, logout: 7},
  {user: H, login: 8, logout: 11},
]

Lets represent the time range of the first user:

  |01 02 03 04 05 06 07 08 09 10|
  |—————————————————————————————|
A |██|██|  |  |  |  |  |  |  |  |
B |  |  |██|  |  |  |  |  |  |  |
C |██|  |  |  |  |  |  |  |  |  |
D |  |  |  |  |  |  |  |  |  |  |
E |██|██|  |  |  |  |  |  |  |  |
F |  |  |  |██|██|██|██|  |  |  |
G |  |  |  |  |██|██|  |  |  |  |
H |  |  |  |  |  |  |  |██|██|██|

We can clearly see that users A, C, and E overlap as well as F with G. How do we determine this programmatically? Analyzing the login and logout times for users A and B we can see that the boundaries only touch themselves but don’t overlap. If we mark the login time for user A as x1 and logout as x2, and login time for user B as y1 and logout as y2 we have that x2 < y1 and x1 < y2.

Seems easy right? But not so fast cowboy, lets analyze F and G:

F |  |  |  |██|██|██|██|  |  |  | Overlapping: No
G |  |██|██|  |  |  |  |  |  |  | Comparison: x2 > y1 ; x1 > y2
  |—————————————————————————————|
F |  |  |  |██|██|██|██|  |  |  | Overlapping: Yes
G |  |  |██|██|  |  |  |  |  |  | Comparison: x2 > y1 ; x1 < y2
  |—————————————————————————————|
F |  |  |  |██|██|██|██|  |  |  | Overlapping: Yes
G |  |  |  |██|██|  |  |  |  |  | Comparison: x2 > y1 ; x1 < y2
  |—————————————————————————————|
F |  |  |  |██|██|██|██|  |  |  | Overlapping: Yes
G |  |  |  |  |██|██|  |  |  |  | Comparison: x2 > y1 ; x1 < y2
  |—————————————————————————————|
F |  |  |  |██|██|██|██|  |  |  | Overlapping: Yes
G |  |  |  |  |  |██|██|  |  |  | Comparison: x2 > y1 ; x1 < y2
  |—————————————————————————————|
F |  |  |  |██|██|██|██|  |  |  | Overlapping: Yes
G |  |  |  |  |  |  |██|██|  |  | Comparison: x2 > y1 ; x1 < y2
  |—————————————————————————————|
F |  |  |  |██|██|██|██|  |  |  | Overlapping: No
G |  |  |  |  |  |  |  |██|██|  | Comparison: x2 < y1 ; x1 < y2

We can see that all the overlapping ranges are defined as x2 > y1 && x1 < y2 while the no overlapping cases are defined as (x2 > y1 && x1 > y2) || (x2 < y1 ; x1 < y2). Notice how the comparison is pointing to the same side in both cases. If we flip F and G we get the same results for the overlapping ranges and the only difference is with the non-overlapping cases were the comparison inverts the position.

So now we have the formula, but iterating a list of objects like in the example would take O(N^2) as we will need to take every user information and compare it with the rest of the cases which for a big dataset will take a considerable amount of time. However, this is irrelevant to the question unless they ask us to optimize the solution a simple iteration will work.

data = json.decode(input)
length = size(data)
for key, node in data:
  printf("%s -> ", node.user)
  for (i = key+1; i < length; i++):
    printf("'%s' ", data[i].user)
  print "\n"

This code will produce a stair-like output, this way we can discard comparisons between ranges that were already checked; if we check A vs. B there is no reason to check B vs. A because the comparison will return the same results.

data = json.decode(input)
length = size(data)
overlapping = 0
for key, node in data:
  for (i = key+1; i < length; i++):
    if node.logout > data[i].login && node.login < data[i].logout:
      overlapping++
print overlapping
Do you have a project idea? Let's make it together!