Calendar Conflicts
Hard
Programming Interview
OOP
24 views
Problem Statement
You're given {x}. Create Calendar class add(start,end) returns YES if added else NO (conflict if overlap). Output results for each add.
Input Format
First line n. Next n lines start end.
Output Format
n lines YES/NO.
Example
4 1 3 3 5 2 4 6 7
YES YES NO YES
Constraints
1
Input / Output Format
Input Format
First line n. Next n lines start end.
Output Format
n lines YES/NO.
Constraints
1
Examples
Input:
4
1 3
3 5
2 4
6 7
Output:
YES
YES
NO
YES
Example Solution (Public)
import sys
lines=sys.stdin.read().splitlines()
if not lines: sys.exit(0)
n=int(lines[0].strip())
class Calendar:
def __init__(self):
self.arr=[]
def add(self,s,e):
i=0
j=len(self.arr)
while i<j:
mid=(i+j)//2
if self.arr[mid][0]<s:
i=mid+1
else:
j=mid
if i>0 and self.arr[i-1][1]>s:
return False
if i<len(self.arr) and e>self.arr[i][0]:
return False
self.arr.insert(i,(s,e))
return True
cal=Calendar()
out=[]
for i in range(1,1+n):
a,b=map(int,(lines[i] if i<len(lines) else '0 0').split())
out.append('YES' if cal.add(a,b) else 'NO')
print('\
'.join(out))
Official Solution Code
import sys
lines=sys.stdin.read().splitlines()
if not lines: sys.exit(0)
n=int(lines[0].strip())
class Calendar:
def __init__(self):
self.arr=[]
def add(self,s,e):
i=0
j=len(self.arr)
while i<j:
mid=(i+j)//2
if self.arr[mid][0]<s:
i=mid+1
else:
j=mid
if i>0 and self.arr[i-1][1]>s:
return False
if i<len(self.arr) and e>self.arr[i][0]:
return False
self.arr.insert(i,(s,e))
return True
cal=Calendar()
out=[]
for i in range(1,1+n):
a,b=map(int,(lines[i] if i<len(lines) else '0 0').split())
out.append('YES' if cal.add(a,b) else 'NO')
print('\
'.join(out))
Please login to submit solutions.