Update: As the problem looks like it need a data structure like cache to hold elements and perform operations. LinkedHashMap may be suitable to implement this as insertion and deletion are easy on it.
- j) ]& B5 M$ V" a Q' s5 g
4 q& H$ P% F Z2 C& l My below code is written using ArrayList and I am creating a result list every time when insert request comes which is not optimal. 7 q1 A5 {' B6 x4 O+ ]8 i
. q3 f' t0 ` Y+ d Previously:2 K8 Z3 R" v6 B" N% x2 X
# |# H! O' t. x0 z Possibility-1: This problem is combination of merge intervals and insert intervals case if the problem says the problem start with list of unsorted intervals.
8 n* i h; f# ]1 R m3 x
5 i# m' _) `4 k/ w- Y9 V' \$ A0 \( a Possibility-2 : If the problem is to assume one interval comes at a time as input, then it is straight forward insert interval case.
8 n- F* |, L. S- C
: q& m5 K: W$ [% X8 V Java Solution:' b2 v9 p) T8 k+ v) x) x2 z6 S6 y
( A7 H" s8 a; Z
Interval object can be stored as below. class Interval{
/ p+ T5 t0 J$ Q int start;
! r8 O' T9 q) _: L+ V7 I int end;
0 @- I0 F/ h$ d7 y* t6 R public Interval(int start, int end){# G1 K% T) P6 w
this.start = start;3 ^1 b0 y p) Q6 P2 Q
this.end = end;6 m7 m8 O, u! r% o% E
}
3 r2 C3 `7 h9 U5 e& ~9 H0 K# j}
Key points:! Y9 J2 B# u. w) ~9 m
1. As the question is not clear, if the intervals are sorted or not incase of more intervals as a preprocessing step.
: c6 E4 @% H' V1 K: E We can take initial List of initial set of inputs and sort them and merge them and keep it ready.
- K0 G: o1 w9 A# j e0 z ( b% G: _4 L: O7 G
This can be a preprocessor step.
* n; O% }# U9 Y5 V! U( H - `/ Z% T& _' Q+ e* M, H* o) f
Merge (preprocess step) can be like below public List<Interval> merge(List<Interval> input){
* }3 z2 ~, _$ W; m4 ^! r r" a! ? List<Interval> results = new ArrayList<Interval>();
9 }: X! E+ n& W! h3 H, ^* O //sort the collection6 r- A" |9 ]: x$ r5 I* M* @5 M8 c
Collections.sort(input,(i,j) -> (i.start = j.start ? (i.end.compareTo(j.end)) : i.start.compareTo(j.start) );
' L9 T! n+ d# }# p" J2 z5 O$ V) V5 |4 d. D3 O. j
//Loop through sorted input and merge2 A& v1 |7 h7 d8 k( u3 ^5 C. Z
Interval previous = null;; T. g0 w+ I! u# ?8 v5 u
for(Interval curr: input){9 P7 Q4 ~6 B2 H7 \$ _ Y: S: H; J
if(previous == null || previous.end < curr.start){ //non-overlap case7 ?9 t+ T# A# b5 A+ Y
if(previous !=null){7 k5 g5 E7 `' C/ ~ a
results.add(previous);( N5 i- u. r6 X7 S' E
}; |: `4 h8 J( Z* ~
previous = new Interval(curr.start, curr.end);1 S. [2 Q) U- y) Q+ L4 \
}else{
s" N! j8 |+ H$ t4 t3 }8 b previous.start = Math.min(previous.start, curr.start);
F+ b$ d" b; R& U8 _4 j previous.end = Math.max(previous.end, curr.end);
8 V3 S; \3 Q$ _% `2 g5 B }
6 P* x: s+ c, S$ \: g }! _6 K* N1 x; A) k5 [6 J$ o
//Very important to add below code to handle last previous interval+ T2 b" T; R2 T( Y Z
if(previous != null){" J, z( m6 G5 q* z2 O/ K, n' o
results.add(previous);
6 O5 C0 N3 o4 c# G5 T+ P }
! L! ]; ?% W. I+ w8 c return results;
X0 f) Z; c& K}
2. After step-1, for every new interval, it is a insert interval scenario (data is already sorted in step-1) public List<Interval> insertAndMerge(List<Interval> input, Interval target){
/ z$ F3 a( |# W
8 B) C& O5 v( Q1 i //handle single element cases here
2 |5 g2 P. k+ X0 R: O$ X! c& x7 h# P if(input.size()==0){
' Q# o$ r; p( Q0 F; X* \ return null;
e' {0 ]5 q' c6 n5 J# j( b4 i }else if(input.get(0).start>target.end || input.get(input.size()-1).end < target.start){ //no overlap) ]) g s4 a" w( k/ h
input.add(target);
0 {4 L+ \& O3 } }else{
8 G4 o: q9 E) e: \ int result = insertAndMerge2(input, 0, input.size() - 1, target);4 o. j+ V% u) l6 l4 Q$ L
if(result == -1){3 x( v ?( Z, }, j' h
input.add(target);7 [. ?5 V9 w0 b! ?
}
" o/ q, l% a. L) s+ m }" W9 x" m" Z3 ~1 P9 F1 |
return input;& H) w1 I( { t$ [* X* ^
}
|