## Google Interview Question

Software Engineers**Country:**United States

```
struct Interval
{
bool operator<(const Interval& in)
{
return left < in.left;
}
int left;
int right;
};
vector<Interval> UnionInverval(const vector<Interval>& A)
{
vector<Interval> ret;
if (A.size() == 0) return ret;
Interval cur(A.front());
for (int i = 1; i < A.size(); i++)
{
if (cur.right >= A[i].left)
{
if (A[i].right > cur.right)
cur.right = A[i].right;
}
else
{
ret.emplace_back(cur);
cur = A[i];
}
}
ret.emplace_back(cur);
return ret;
}
bool IsIntervalCovered(vector<Interval> A, const Interval& a)
{
sort(A.begin(), A.end());
bool ret = false;
vector<Interval> union_A = UnionInverval(A);
int left = 0, right = union_A.size() - 1;
while (left <= right)
{
int m = left + (right - left) / 2;
if (union_A[m].left == a.left) {
ret = a.right <= union_A[m].right;
break;
}
else if (union_A[m].left < a.left) {
left = m + 1;
if (m + 1 < union_A.size() && union_A[m + 1].left > a.left)
{
ret = a.right <= union_A[m].right;
break;
}
}
else
{
right = m - 1;
if (m - 1 >= 0 && union_A[m - 1].left <= a.left)
{
ret = a.right <= union_A[m - 1].right;
break;
}
}
}
return ret;
}
int main()
{
vector<Interval> A;
A.emplace_back(Interval{ 2,5 });
A.emplace_back(Interval{ 5,7 });
A.emplace_back(Interval{ 1,4 });
Interval a{ 1, 6 };
bool ret = IsIntervalCovered(A, a);
A.clear();
A.emplace_back(Interval{ 1,4 });
A.emplace_back(Interval{ 6,7 });
A.emplace_back(Interval{ 2,5 });
a = { 2, 6 };
ret = IsIntervalCovered(A, a);
a = { 0, 4 };
ret = IsIntervalCovered(A, a);
return 0;
}
```

What is meant by interval is covered? Are these coordinates of a triangle and they are asking if the point is inside?

- Denis July 05, 2019