The given solution of this problem is good and easy to implement.
I found a better way of using binary search. It only uses two times binary searches (at most), and three times array copy.
My idea is: The input is sorted by start position. So we can use binary search to find where the element need to be added should be, and we can use another binary search to find out where the element should end. All the elements between the two position should become a single element, and elements beyond them won’t change.
For example:
Input:
[0, 1], [2, 3], [4, 5], [6, 7], [8, 9].
Add: [2, 7].
first binary search will get 1, means new element should start at 1 (Actually, we need to check the end position of previous element to make sure whether the element intersect with previous element),
second binary search will get -5. means the insertion position should be 4,the new element should end at 3 (element before 4).
Output (keep [0, 1], new element : [2, 7], keep [8,9]).
It’s only 2O(logn) + array copy overhead, We can think array copy operation is faster than o(n). It should be faster than the given solution.
My java code:
public class Solution
{
private static class IntervalComparator implements Comparator<Interval>
{
@Override
public int compare(final Interval o1, final Interval o2)
{
return Integer.compare(o1.getStart(), o2.getStart());
}
}
private static IntervalComparator COMPARATOR = new IntervalComparator();
Interval[] add(final Interval[] items, final Interval item)
{
Interval[] result;
int startPos = Arrays.binarySearch(items, item, COMPARATOR);
startPos = (startPos >= 0) ? startPos : -(startPos + 1);
// The new element should be at tail.
if (startPos == items.length)
{
result = Arrays.copyOf(items, items.length + 1);
result[startPos] = item;
}
else
{
// Previous item intersects with the added one.
if (startPos > 0 && items[startPos - 1].getEnd() >= item.getStart())
{
--startPos;
}
// Start value of the new element.
final int start = Math.min(item.getStart(), items[startPos].getStart());
// Search the position with end value of added element.
int endPos = Arrays.binarySearch(items, startPos, items.length, new Interval(item.getEnd(), 0), COMPARATOR);
// End value of the new element.
final int end;
// There's an element with same start value, so it intersects with the added one.
if (endPos >= 0)
{
end = items[endPos].getEnd();
++endPos;
}
else
{
endPos = -(endPos + 1);
if (0 < endPos)
{
// The previous element may have larger end value.
end = Math.max(item.getEnd(), items[endPos - 1].getEnd());
}
else
{
end = item.getEnd();
}
}
// The result array will be [0, startPos), new element, [endPos, item.length).
result = new Interval[items.length - endPos + startPos + 1];
System.arraycopy(items, 0, result, 0, startPos);
result[startPos] = new Interval(start, end);
System.arraycopy(items, endPos, result, startPos + 1, items.length - endPos);
}
return result;
}
}`indent preformatted text by 4 spaces`