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
7 months ago
  • 8da57acFix minor bugs found by the code static ana…
7 months ago
  • caa417fAdd option to configure the malware scanner…
7 months ago
  • 9c86744Modify default value for some of the alert …
7 months ago
  • 84dd39dAdd option to stop sending the failed login…
7 months ago
  • eb05935Add pre-checks for every plugin page for si…
7 months ago
  • d21a062Modify mechanism to ignore files from integ…
7 months ago
  • b1a9169Add developer option to disable failed pass…
7 months ago
  • 4e3ef13Add support for other English and Spanish b…
7 months ago
  • 2d07b4eFix error interception for Firewall API err…
7 months ago
pushed to master at cixtor/slackapi
  • 4a2c1c8Modify data type for methods related to cha…
  • 6716199Add CLI handler for the users.identity API …
  • f9c448dAdd CLI handler for the mpim.open API endpo…
  • 305d1c4Add CLI handler for the mpim.mark API endpo…
  • 8bb89afAdd CLI handler for the mpim.close API endp…
  • 202a017Add CLI handler for the dnd.teamInfo API en…
  • 68819e9Add CLI handler for the dnd.info API endpoi…
  • 9a2b29aAdd CLI handler for the dnd.endSnooze API e…
  • e7dc86aAdd CLI handler for the dnd.setSnooze API e…
  • 111c53fAdd CLI handler for the dnd.endDnd API endp…
  • cdb620dFix token usage when there are no extra par…
  • View comparison for these 11 commits
7 months ago
pushed to master at cixtor/slackapi
7 months ago
  • 6497e80Remove unnecessary automatic blacklisting o…
7 months ago
opened pull request Sucuri/sucuri-wordpress-plugin#40
Fix multiple bugs with the API calls and queue system
18 commit with 793 additions and 293 deletion
7 months ago
7 months ago
7 months ago
  • 38cc02aModify timing for the dashboard alerts afte…
7 months ago
  • 350c074Fix infinite loop with email alerts and SMT…
7 months ago
  • acff4aaFix detection of base URL with built-in fun…
7 months ago
7 months ago
7 months ago
7 months ago
7 months ago
opened pull request Sucuri/sucuri-wordpress-plugin#39
Add queue system for the security logs and cache improvement
5 commit with 517 additions and 541 deletion
7 months ago
7 months ago
  • 4c51445Fix static function call of non-static Site…
7 months ago
7 months ago
  • af47581Add changelog to release version 1.8.6
7 months ago
opened pull request Sucuri/sucuri-wordpress-plugin#38
Add changelog to release version 1.8.5
6 commit with 4062 additions and 1841 deletion
7 months ago
  • dc1a05aAdd changelog to release version 1.8.5
7 months ago
Do you have a project idea? Let's make it together!