-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathMyCalendarTwo.java
More file actions
120 lines (99 loc) · 2.52 KB
/
MyCalendarTwo.java
File metadata and controls
120 lines (99 loc) · 2.52 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
import java.util.ArrayList;
import java.util.List;
class MyCalendarTwo
{
class Interval
{
int _start, _end;
public Interval( int start, int end )
{
_start = start;
_end = end;
}
}
// 1 for 1st insert
List<Interval> _list1 = new ArrayList<>(),
// 2 for double counting
_list2 = new ArrayList<>();
boolean intersect( Interval i1, Interval i2 )
{
if ( i1._start >= i2._end || i1._end <= i2._start )
// do NOT intersect
return false;
// do intersect
return true;
}
Interval intersection( Interval i1, Interval i2 )
{
Interval shrink = new Interval( i1._start, i1._end );
shrink._start = Math.max( i1._start, i2._start );
shrink._end = Math.min( i1._end, i2._end );
return shrink;
}
public MyCalendarTwo()
{
}
Interval[] separate( Interval i1, Interval i2 )
{
// will result in 1 interval if start / end equals
// else 2 intervals
Interval[] re = new Interval[2];
if ( i1._start >= i2._start )
{
Interval i = i2;
i2 = i1;
i1 = i;
}
re[0] = i1._start == i2._start ? null : new Interval( i1._start, i2._start );
re[1] = i1._end == i2._end ? null : new Interval( Math.min( i1._end, i2._end ), Math.max( i1._end, i2._end ) );
return re;
}
public boolean book( int start, int end )
{
Interval n = new Interval( start, end );
for ( Interval i : _list2 )
{
// simply can't add due to third counting
if ( intersect( i, n ) )
return false;
}
// check if new interval intersects with any current interval
boolean flag = false;
List<Interval> nList = new ArrayList<>();
for ( Interval i : _list1 )
{
// updates intersecting intervals
if ( intersect( i, n ) )
{
flag = true;
// intersection part goes into list 2,
_list2.add( intersection( i, n ) );
// rest goes into 1
for ( Interval sep : separate( i, n ) )
{
if ( sep != null )
nList.add( sep );
}
}
else
nList.add( i );
}
if ( !flag )
nList.add( n );
_list1 = new ArrayList<>( nList );
return true;
}
public static void main( String[] args )
{
String[] op = { "MyCalendarTwo", "book", "book", "book", "book", "book", "book" };
int[][] v = { {}, { 10, 20 }, { 50, 60 }, { 10, 40 }, { 5, 15 }, { 5, 10 }, { 25, 55 } };
MyCalendarTwo myCalendar = new MyCalendarTwo();
for ( int i = 1; i < op.length; i++ )
System.out.println( myCalendar.book( v[i][0], v[i][1] ) );
}
}
/**
* Your MyCalendarTwo object will be instantiated and called as such:
* MyCalendarTwo obj = new MyCalendarTwo();
* boolean param_1 = obj.book(start,end);
*/