Calendar Conflicts
Programming Interview
Hard
9 views
Problem Description
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.
Official Solution
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))
Solutions (0)
No solutions submitted yet. Be the first!
No comments yet. Start the discussion!