Zonal Computing Olympiad 2015, 29 Nov 2014

An interval is a pair of positive integers [a, b] with a ≤ b. It is meant to denote the set of integers that lie between the values a and b. For example [3,5] denotes the set {3,4,5} while the interval [3, 3] denotes the set {3}.

We say that an interval [a, b] is covered by an integer i, if i belongs to the set defined by [a, b]. For example interval [3, 5] is covered by 3 and so is the interval [3, 3].

Given a set of intervals I, and a set of integers S we say that I is covered by S if for each interval [a, b] in I there is an integer i in S such that [a, b] is covered by i. For example, the set {[3, 5], [3, 3]} is covered by the set {3}. The set of intervals {[6, 9], [3, 5], [4, 8]} is covered by the set {4, 5, 8}. It is also covered by the set {4, 7}.

We would like to compute, for any set of intervals I, the size of the smallest set S that covers it. You can check that for the set of intervals {[6, 9], [3, 5], [4, 8]} the answer is 2 while for the set of intervals {[3, 5], [3, 3]} the answer is 1.

Your program should take the set of intervals as input and output the size of the smallest set that covers it as the answer.

-----Input format-----
The first line contains a single integer N, giving the number of intervals in the input.

This is followed by N lines, each containing two integers separated by a space describing an interval, with the first integer guaranteed to be less than or equal to the second integer.

-----Output format-----
Output a single integer giving the size of the smallest set of integers that covers the given set of intervals.

-----Test data-----
You may assume that all integers in the input are in the range 1 to 10^8 inclusive.

Subtask 1 (100 marks) : 1 ≤ N ≤ 5000.

-----Sample Input 1-----
2 
3 5 
3 3

-----Sample Output 1-----
1

-----Sample Input 2-----
3 
6 9 
3 5 
4 8

-----Sample Output 2-----
2

Difficulty: interview

Starter code:

Solutions:
# cook your dish here

import operator

no_seq = int(input().strip())
seqs = []
for idx in range(no_seq):
    input_now = input().strip().split(" ")
    seqs.append([int(input_now[0]), int(input_now[1])])

seqs.sort(key=operator.itemgetter(0))
curr = seqs[0]
answer = 1
for i in range(1, no_seq):
    if curr[1] < seqs[i][0]:
        answer += 1
        curr = seqs[i]
    else:
        curr[0] = seqs[i][0]
        curr[1] = min(curr[1], seqs[i][1])

print(answer)


# cook your dish here
from operator import itemgetter
n=int(input())
array=[]
for _ in range(n):
    array.append(list(map(int, input().split())))
array.sort(key=itemgetter(1))
array.sort(key=itemgetter(0))
appo=array[0]
counter=1
for i in range(1,n):
    if appo[1]<array[i][0]:
        counter+=1
        appo=array[i]
    else:
        appo[0] = array[i][0]
        appo[1] = min(appo[1], array[i][1])
print(counter)

# cook your dish here
n=int(input())
def compare(tpl):
	return tpl[1]
points=[]
for i in range(n):
	a,b=map(int,input().split())
	points.append((a,b))
ans=1
points.sort(key=compare)
end=points[0][1]
for a,b in points:
	if a>end:
		ans+=1
		end=b
print(ans)

n=int(input())
def compare(tpl):
	return tpl[1]
points=[]
for i in range(n):
	a,b=list(map(int,input().split()))
	points.append((a,b))
ans=1
points.sort(key=compare)
end=points[0][1]
for a,b in points:
	if a>end:
		ans+=1
		end=b
print(ans)
		


t=int(input())
l=[]
for i in range(t):
    l.append([int(i) for i in input().split()])
l.sort(key = lambda x: x[1])
last=l[0][1]
count=1
for i in range(1,t):
    if l[i][0]>last:
        count+=1
        last=l[i][1]
print(count)

t=int(input())
l=[]
for i in range(t):
    l.append([int(i) for i in input().split()])
l.sort(key = lambda x: x[1])
last=l[0][1]
count=1
for i in range(1,t):
    if l[i][0]>last:
        count+=1
        last=l[i][1]
print(count)

import sys

N=int(sys.stdin.readline())

arr=[]
for i in range(N):
	[L,R]=[int(i) for i in sys.stdin.readline().split()]
	arr.append([R,L])

arr.sort()
last = arr[0][0]
count=1

for c in range(1,N):
	if(arr[c][1]>last):
		count+=1
		last=arr[c][0]

print(count)



N = int(input())
intervals = []
for i in range(N):
    intervals.append(list(map(int, input().split()))[-1::-1])

intervals.sort()
mx = intervals[0][0]
count = 1
for i in range(1,N):
    if intervals[i][1] > mx:
        count += 1
        mx = intervals[i][0]
print(count)


# cook your dish here
n=int(input())
c=[]
m=n
while(n>0):
    a,b=input().split()
    a=int(a)
    b=int(b)
    c.append([a,b])
    n=n-1
c.sort()
f=0
s=1
total=1
while(f<m-1):
    while(s<m):
        if(c[f][1]<c[s][0]):
            total=total+1
            f=s
            s=s+1
        elif((c[f][1]>=c[s][0]) and (c[f][1]>=c[s][1])):
            f=s
            s=s+1
        else:
            s=s+1
    f=f+1
        
print(total)
        
            
        
    


n = int(input())
lst = [list(map(int,input().split())) for i in range(n)]
lst.sort(key = lambda i: i[1])
res = 1
t = lst[0]
for i in range(1,n):
    if lst[i][0] > t[1]:
        res += 1
        t = lst[i]
print(res)

n = int(input())
x = [list(map(int,input().split())) for i in range(n)]
x.sort(key = lambda i: i[1])
ans = 1
t = x[0]
for i in range(1,n):
    if x[i][0] > t[1]:
        ans += 1
        t = x[i]
print(ans)

import sys 
input = sys.stdin.readline 

N=int(input())
arr=[]
for i in range(N):
    k=list(map(int,input().split()))
    arr.append(k)
arr.sort()
end=arr[0][1]
count=1 
for j in range(1,len(arr)):
    if(arr[j][0]<=end):
        if(arr[j][1]<=end):
            end=arr[j][1]
        else:
            pass 
    else:
        count+=1 
        end = arr[j][1]
print(count)


import collections


def solve(sets):
    n = len(sets)
    sets.sort(key=lambda x: x[0])

    s, f = sets[0][0], sets[0][1]
    ans = 1

    for i in range(1, n):
        if sets[i][0] <= f:
            s = max(s, sets[i][0])
            f = min(f, sets[i][1])
        else:
            ans += 1
            s = sets[i][0]
            f = sets[i][1]

    return ans


n = int(input().strip())
sets = []
# [n,m] = list(map(int, input().strip().split()))

for i in range(n):
    sets.append(list(map(int, input().strip().split())))

print(solve(sets))


#for _ in range(int(input())):
#dt = {} for i in x: dt[i] = dt.get(i,0)+1
#dt = {k:v for k,v in sorted(x.items(), key=lambda i: i[1])}
ipnl = lambda n: [int(input()) for _ in range(n)]
inp = lambda :int(input())
ip = lambda :[int(w) for w in input().split()]
mp = lambda :list(map(int,input().split()))

n = inp()
x = []
for i in range(n):
    x.append([int(w) for w in input().split()])
x.sort(key = lambda i:i[1])
visited = {}
ctr = 1
t = x[0]
visited[0] = 1
for i in range(1,n):
    if not visited.get(i,0):
        visited[i] = 1
        if x[i][0] > t[1]:
            ctr += 1
            t = x[i]
print(ctr)


n = int(input())

chu = []
bs = []

mi = -1
count = 0

for _ in range(n):
	x,k = map(int, input().split())
	chu.append([x,k])

chu.sort()

for i in range(n):
	x = chu[i][0]
	k = chu[i][1]

	if x <= mi:
		mi = min(mi, k)
	else:
		count += 1
		mi = k

	#print(bs,chu)
print(count)

intput = lambda: [int(i) for i in input().split()]
# Write your code here
n = int(input())
l = sorted([intput() for i in range(n)])
i = res = 0
while i < n:
    k = l[i][1]
    while i < n and k >= l[i][0]:
        i += 1
        if i < n and k > l[i][1]:
            k = l[i][1]
    res += 1
print(res)

def main():
	from sys import stdin, stdout
	rl = stdin.readline

	n = int(rl())
	a = [[int(x) for x in rl().split()] for _ in range(n)]

	a.sort()
	i = s = 0
	while i < n:
		end = a[i][1]
		while i < n and end >= a[i][0]:
			i += 1
			end = min(end, a[i][1]) if i < n else end
		s += 1

	stdout.write(str(s))


main()

def main():
	from sys import stdin, stdout
	rl = stdin.readline

	n = int(rl())
	a = [[int(x) for x in rl().split()] for _ in range(n)]

	a.sort()
	i = s = 0
	while i < n:
		end = a[i][1]
		while i < n and end >= a[i][0]:
			i += 1
			end = min(end, a[i][1]) if i < n else end
		s += 1

	stdout.write(str(s))


main()
    


from operator import itemgetter

N = int(input())
L = []
for n in range(N):
    L.append([int(x) for x in input().split()])
L.sort(key=itemgetter(1))
# print(L)

cnt = 0
while L:
    m = L[0][1]
    L = [l for l in L if l[0] > m]
    cnt += 1
    # print(L)
print(cnt)
        


# cook your dish here
n=int(input())
arr=[]
for i in range(n):
    arr.append([int(i) for i in input().split()])
arr.sort()
ans=1
i=0
p=arr[0][0]
q=arr[0][1]
while(i<n-1):
    i+=1
    if(arr[i][0]<=q):
        q=min(q,arr[i][1])
    else:
        ans+=1 
        q=arr[i][1]
print(ans)


n= int(input())
l=[]

for i in range(n):
    l.append(list(map(int,input().split())))

l.sort(key = lambda x: x[1])
count=1
R = l[0][1]
for i in l:
    if not(i[0]<= R<= i[1]):
        R = i[1]
        count+=1

print(count)


n= int(input())
l=[]

for i in range(n):
    l.append(list(map(int,input().split())))

l.sort(key = lambda x: x[1])
count=1
last = l[0][1]
for i in l:
    if not(i[0]<= last<= i[1]):
        last = i[1]
        count+=1
print(count)




n = int(input())
lr = sorted(tuple(map(int, input().split())) for _ in range(n))

i = 0
c = 0

while i < n:
    x = lr[i][1]

    while i < n and lr[i][0] <= x:
        if lr[i][1] < x:
            x = lr[i][1]

        i += 1
        
    c += 1

print(c)


from sys import stdin
n = int(stdin.readline())
sets = []
for i in range(n):
    sets.append(tuple(map(int, stdin.readline().split())))
sets.sort()
ans = 1
last_end = sets[0][1]
for i in range(1, len(sets)):
    if last_end < sets[i][0]:
        ans += 1
        last_end = sets[i][1]
    else:
        last_end = min(last_end, sets[i][1])
print(ans)