- Check two interval overlap
- Merge two Intervals;
- Insert an Interval to a sorted Non-overlap intervals list
- Merge one list of sorted possible overlap interval
- Merge two list of sorted non overlap intervals.
- Check one interval covers one List of intervals
- Check a list of intervals fully covers one interval
- Subtract one interval from another
- Subtract one interval from a sorted interval List.
1.Check two interval overlap
public boolean overlap(Interval itv1, Interval itv2) {
return !(itv1.end <= itv2.start || itv1.start >= itv2.end);
}
- Merge two intervals;
public Interval mergeTwoInterval(Interval itv1, Interval itv2) {
if (!overlap(itv1, itv2)) return null;
return new Interval(Math.min(itv1.start, itv2.start),
Math.max(itv1.end, itv2.end));
}
- Insert an Interval to a sorted Non-overlap intervals list
Leetcode 57
public List<Interval> insert(List<Interval> intervals, Interval newInterval) {
Interval holder = new Interval(newInterval.start, newInterval.end);
List<Interval> ans = new ArrayList<>();
boolean alreadyDone = false;
for (Interval itv : intervals) {
if (itv.end < holder.start) {
ans.add(itv);
} else if (itv.start > holder.end) {
if (!alreadyDone) {
ans.add(holder);
alreadyDone = true;
}
ans.add(itv);
} else {
holder.start = Math.min(holder.start, itv.start);
holder.end = Math.max(holder.end, itv.end);
}
}
if (!alreadyDone) ans.add(holder);
return ans;
}
}
