Finding the XOR between multiple lists of no overlapping time intervals (Java)
Posted by nick898@reddit | learnprogramming | View on Reddit | 4 comments
Does any one have any elegant solution for finding the XOR between two lists of time intervals, preferably in Java? You can assume that, within each list, the time intervals are non-overlapping, but it is not safe to assume that between the two lists they are non-overlapping. I’ve been struggling with it the past couple of days.
CatSwolo@reddit
What exactly do you mean by XOR between 2 lists of time intevals? Do you mean a merge or a union between those 2 lists?
What you can do is simply explain, what you want to achieve with those 2 lists of time intervals.
nick898@reddit (OP)
An XOR between 2 lists of time intervals (list A and list B) is all of the time that is exclusively in either list A or in list B, but not both.
CatSwolo@reddit
If thats the case then you can simply take the starting datetime from both intervals (lets define
i1 = [s1, e1) , i2 = [s2, e2)) then you first have to check if they intersect with each other (if s1 < e2 v s2 < e1 then they intersect). If they dont intersect then give back those 2 existing intervals else give back interval with starting values from both intervalsif e1 == e2 then null else if s1 < s2 then [s1, s2) else [s2, s1)and ending values from both intervalsif e1 == e2 then null else if e1 < e2 then [e1, e2) else [s2, e1). If the result of those are not null then add them into a list and return it. This only works with 2 time intervals, but not with 3.nick898@reddit (OP)
I get that I’m asking about the general case where you have two lists of intervals instead of two intervals.
You should also be able to solve this by finding the intersection between the two lists and subtract each common interval from every interval in each of the lists, union it up, and that should give you the XOR between the two lists. This might be easier for me to try instead of XORing pairs of intervals.