So, I seen this problem in 4-5 interview L3/L4 experiences and just wanted to share it's description and solution in proper format which I was able to build up from those experiences also I will be giving few testcases incase you want to test yourself.
Many people are confusing with Leetcode 986. Interval List Intersections however that's lot different from it.
Google Question. Set Difference of Floating-Point Ranges
Problem Statement
You are given two lists, a and b, where each list contains non-overlapping floating-point intervals sorted in ascending order.
Each interval can be represented in one of four formats:
[start, end]includes bothstartandend.[start, end)includesstartbut excludesend.(start, end]excludesstartbut includesend.(start, end)excludes bothstartandend.
Your task is to compute the set difference of a - b, meaning you should return the values in a that do not overlap with any interval in b. The result should be a list of non-overlapping intervals in sorted order while preserving the correct interval inclusion/exclusion format.
Example 1:
Input:
a = [[2.5, 7.5), (9.0, 10.4]]
b = [(4.3, 9.3), [9.5, 11.0)] Output:
[[2.5, 4.3], [9.3, 9.5)] Explanation:
- The first interval
[2.5, 7.5)fromaoverlaps with(4.3, 9.3), so the remaining non-overlapping part is[2.5, 4.3]. - The second interval
(9.0, 10.4]fromaoverlaps with[9.3, 9.3](trivial) and[9.5, 11.0). The remaining non-overlapping part is[9.3, 9.5).
Example 2:
Input:
a = [(1.0, 5.0)]
b = [[2.0, 3.0), (4.0, 6.0)] Output:
[(1.0, 2.0), [3.0, 4.0]]Constraints:
1 ≤ len(a), len(b) ≤ 10^4a[i] = [start, end],[start, end),(start, end], or(start, end)where0 ≤ start < end ≤ 10^9b[i] = [start, end],[start, end),(start, end], or(start, end)where0 ≤ start < end ≤ 10^9aandbcontain non-overlapping intervals within themselves and are sorted in increasing order bystart.- The output must also be a list of non-overlapping intervals in increasing order, preserving the correct inclusion/exclusion format.
Follow-Up:
- What is given lists
aandbwere not sorted and also if they were overlapping? What additional steps you would have taken?
Template Code:
class Value {
public:
bool isIncluded;
float value = 0;
};
class Interval {
public:
Value start, end;
};
class RangeUtility{
public:
vector<Interval> removeFromList(vector<Interval> A, vector<Interval> B) {
// return []
}
}
My Solution
Time Complexity O(n*logn)
Space Complexity O(1)
Still figuring out a cleaner and shorter way though.
bool isIntervalValid(Interval interval){
if(interval.start.value > interval.end.value) return false;
if(interval.start.value == interval.end.value && (!interval.start.isIncluded || !interval.end.isIncluded)) return false;
return true;
}
vector<Interval> removeFromList(vector<Interval> A, vector<Interval> B) {
const int m = A.size(), n = B.size();
// Sort and merge overlapping intervals as extra solve to reduce follow up to base question.
sort(A.begin(), A.end(), [](auto& a, auto& b){a.start.value < b.start.value;});
sort(B.begin(), B.end(), [](auto& a, auto& b){a.start.value < b.start.value;});
A = mergeIntervals(A);
B = mergeIntervals(B);
vector<Interval> differenceList;
float lastBEndedAt = -1;
bool wasLastBIncluded = false;
int it = 0, jt = 0;
while(it < m && jt < n) {
Interval currentInterval;
if(A[it].start.value > lastBEndedAt) {
currentInterval.start = Value{A[it].start.isIncluded, A[it].start.value};
} else {
currentInterval.start = Value{!wasLastBIncluded, lastBEndedAt};
}
if(B[jt].start.value <= A[it].end.value) {
currentInterval.end = Value{!B[jt].start.isIncluded, B[jt].start.value};
} else {
currentInterval.end = Value{A[it].end.isIncluded, A[it].end.value};
}
if(isIntervalValid(currentInterval)) {
differenceList.push_back(currentInterval);
}
if(A[it].end.value < B[jt].end.value) {
it++;
} else {
lastBEndedAt = B[jt].end.value;
wasLastBIncluded = B[jt].end.isIncluded;
jt++;
}
}
// if anything pending.
if(it < m) {
Interval extraInterval;
if(lastBEndedAt >= A[it].start.value) {
extraInterval.start = Value{!wasLastBIncluded, lastBEndedAt};
}
else {
extraInterval.start = Value{A[it].start.isIncluded, A[it].start.value};
}
extraInterval.end = Value{A[it].end.isIncluded, A[it].end.value};
if(isIntervalValid(extraInterval)) {
differenceList.push_back(extraInterval);
}
it++;
}
// add extra intervals A had.
while(it < m) {
Interval currentInterval;
currentInterval.start = Value{A[it].start.isIncluded, A[it].start.value};
currentInterval.end = Value{A[it].end.isIncluded, A[it].end.value};
differenceList.push_back(currentInterval);
it++;
}
return differenceList;
}Additional Test Cases
Example 1
Input:
a = [[2.5, 7.5)]
b = [[4.3, 9.3)]Output:
[[2.5, 4.3)]Example 2
Input:
a = [[2.5, 9.5)]
b = [[4.5, 6.5)]Output:
[[2.5, 4.5), [6.5, 9.5)]Example 3
Input:
a = [[1, 3)]
b = [[4, 6)]Output:
[[1, 3)]Example 4
Input:
a = [[3, 5)]
b = [[1, 7)]Output:
[]Example 5
Input:
a = [[1, 8)]
b = [[3, 6)]Output:
[[1, 3), [6, 8)]Example 6
Input:
a = [[1, 3), [5, 8)]
b = [[2, 6)]Output:
[[1, 2), [6, 8)]Example 7
Input:
a = [[1, 5]]
b = [[3, 5)]Output:
[[1, 3), [5, 5]]Example 8
Input:
a = [[2, 6)]
b = [[1, 7)]Output:
[]Example 9
Input:
a = [[1, 3), [7, 9)]
b = [[4, 6)]Output:
[[1, 3), [7, 9)]Example 10
Input:
a = [[1, 3)]
b = [[3, 5)]Output:
[[1, 3)]Example 11
Input:
a = [[1, 5), [6, 9)]
b = [[2, 7)]Output:
[[1, 2), [7, 9)]Example 12
Input:
a = [[2.5, 9.5)]
b = [[4.5, 6.5), [7, 8)]Output:
[[2.5, 4.5), [6.5, 7), [8, 9.5)]Example 13
Input:
a = [[1, 5), [6, 9)]
b = [[1, 5)]Output:
[[6, 9)]Example 14
Input:
a = [[1, 5)]
b = [[1.5, 3)]Output:
[[1, 1.5), [3, 5)]Example 15
Input:
a = [[2, 6)]
b = [[4, 6)]Output:
[[2, 4)]Example 16
Input:
a = [[5, 8)]
b = [[2, 5)]Output:
[[5, 8)]Example 17
Input:
a = [[1, 10]]
b = [[1, 10)]Output:
[[10, 10]]Example 18
Input:
a = [[1, 5)]
b = [[10, 15)]Output:
[[1, 5)]Let me know if there any errors in testcase you think