Problem:
 Score : 400 points    Problem Statement There are N islands lining up from west to east, connected by N-1 bridges.  The i -th bridge connects the i -th island from the west and the (i+1) -th island from the west.  One day, disputes took place between some islands, and there were M requests from the inhabitants of the islands:  Request i : A dispute took place between the a_i -th island from the west and the b_i -th island from the west. Please make traveling between these islands with bridges impossible.  You decided to remove some bridges to meet all these M requests.  Find the minimum number of bridges that must be removed.      Constraints  All values in input are integers.  2 \leq N \leq 10^5  1 \leq M \leq 10^5  1 \leq a_i < b_i \leq N  All pairs (a_i, b_i) are distinct.         Input Input is given from Standard Input in the following format:  N  M  a_1  b_1  a_2  b_2  :  a_M  b_M       Output Print the minimum number of bridges that must be removed.        Sample Input 1 5 2
1 4
2 5      Sample Output 1 1  The requests can be met by removing the bridge connecting the second and third islands from the west.       Sample Input 2 9 5
1 8
2 7
3 5
4 6
7 9      Sample Output 2 2       Sample Input 3 5 10
1 2
1 3
1 4
1 5
2 3
2 4
2 5
3 4
3 5
4 5      Sample Output 3 4

Solution (Python):

from operator import itemgetter

n,m = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(m)]
ab.sort(key=itemgetter(1,0))

cnt = 0
cb = -1
for (a,b) in ab:
    if cb == -1:
        cb = b - 1
        cnt += 1
    elif a<=cb:
        continue
    else:
        cb = b - 1
        cnt += 1

print(cnt)

Solution (Python):
N,M=map(int,input().split(" "))
wars=[list(map(int,input().split(" ")))for _ in range(M)]

wars.sort(key=lambda x:x[1])

count=0
before=0

for ai,bi in wars:
    if before>ai:
        continue
        
    before=bi
    count=count+1

print(count)

Solution (Python):
n, m = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(m)]
ab.sort(key=lambda x:x[0], reverse=True)
last_removed = 1000000
ans = 0
for i in range(m):
	if ab[i][1] <= last_removed:
		last_removed = ab[i][0]
		ans += 1
print(ans)

Solution (Python):
import bisect
iipt=lambda:int(input())
miipt=lambda:list(map(int,input().split(" ")))
n, m=miipt()
a=[]
done=[0]*m
for i in range(m):
    a.append(miipt())
b=sorted(a, key=lambda x:x[1])
c=0
d=-1
for p, q in b:
    if not p<=d<q:
        c+=1
        d=q-1
print(c)

Solution (Python):
if __name__ == '__main__':
    N, M = list(map(int, input().split(" ")))

    temp = [list(map(int, input().split(" "))) for i in range(M)]
    s_list = [temp[i][0] for i in range(M)]
    t_list = [temp[i][1] for i in range(M)]

    ans = 0
    bridge = 0
    for ele in sorted(enumerate(t_list), key=lambda x: x[1]):
        if s_list[ele[0]] > bridge:
            bridge = ele[1]-1
            ans += 1

    print(ans)

Solution (Python):
from operator import attrgetter


class Line:
    def __init__(self, a, b):
        self.a = a
        self.b = b


N, M = map(int, input().split())
lines = []
for _ in range(M):
    a, b = map(int, input().split())
    lines.append(Line(a, b))

lines = sorted(lines, key=attrgetter("a"))

start_num = lines[0].a
min_num = 1000000
cnt = 0

for line in lines:
    if line.a != start_num:
        if min_num <= line.a:
            cnt += 1
            min_num = line.b
        start_num = line.a
    if line.b < min_num:
        min_num = line.b
cnt += 1
print(cnt)

Solution (Python):
import sys
input = sys.stdin.readline

N, M = (int(i) for i in input().split())

hasis = []
for i in range(M):
    a, b = (int(i) for i in input().split())
    hasis.append((b , a))
hasis.sort()

cc = 0
now = 0
temp = 0
for hasi in hasis:
    now = hasi[0]
    if hasi[1] <= temp < hasi[0]:
        pass
    else:
        temp = now -1
        cc += 1

print(cc)

Solution (Python):
N, M = map(int, input().split())
E = list([list(map(int, input().split())) for _ in range(M)])

E = sorted(E, key=lambda x: x[1])

removed = -1
ret = 0

for e in E:
    if e[0] > removed:
        ret += 1
        removed = e[1] - 1

print(ret)

Solution (Python):
N, M = map(int, input().split())
AB = [list(map(int, input().split())) for i in range(M)]


ans = 0
AB = sorted(AB, key=lambda x: x[1])
last = 0
for i, v in enumerate(AB):
    if last < v[0]:
        last = v[1]-1
        ans += 1


print(ans)

Solution (Python):
N,M = map(int,input().split())
x = [list(map(int,input().split())) for i in range(M)]
x.sort(key=lambda x:x[1])
ans,m = 0,0

for a,b in x:
    if a>=m:
        ans += 1
        m = b
print(ans)

Solution (Python):

from collections import deque
N, M = map(int, input().split())
abn = [list(map(int, input().split())) for _ in range(M)]

abn.sort(key=lambda x:x[1])

ans = 0
bnum = -1
for a,b in abn:
    if bnum == -1:
        bnum = b - 1
        ans += 1
    elif a <= bnum < b:
        continue
    else:
        bnum = b - 1
        ans += 1

print(ans)

Solution (Python):

from collections import deque
N, M = map(int, input().split())
abn = [list(map(int, input().split())) for _ in range(M)]

abn.sort(key=lambda x:x[1])

ans = 0
bnum = -1
for a,b in abn:
    if bnum == -1:
        bnum = b - 1
        ans += 1
    elif a <= bnum < b:
        continue
    else:
        bnum = b - 1
        ans += 1

print(ans)

Solution (Python):

N,M = list(map(int,input().split()))
Map = [[] for i in range(N)]
for i in range(M):
    a,b=list(map(int,input().split()))
    Map[a-1].append(b-1)

b_list = [0 for i in range(N)]
count=0   
for i in range(N):
    if b_list[i]==1:
        b_list=[0 for i in range(N)]
        count+=1
    for j in Map[i]:
        b_list[j]=1

print(count)

Solution (Python):
n, m = map(int, input().split())
p = list()
for i in range(m):
    a, b = map(int, input().split())
    p.append((b, a))
p = sorted(p)
broken = -1
ans = 0
for item in p:
    a = item[1]
    b = item[0]
    if a >= broken:
        ans += 1
        broken = b
print(ans)

Solution (Python):
n,m = map(int,input().split())
lis = [list(map(int,input().split())) for i in range(m)]
lis.sort(key=lambda x: x[1])
ans = 0
cou = 0
for num,nu in lis:
  if cou <= num:
    ans += 1
    cou = nu
print(ans)

Solution (Python):
n, m = map(int, input().split())
c = []
for i in range(m):
    c.append([int(m) for m in input().split()])
c.sort(key=lambda x:(x[0], x[1]))
p = []
q = []
for i in range(n):
    p.append(0)
    q.append(0)
j = 0
count = 0
for i in range(m):
    if i == 0:
        p[j] = c[i][0]
        q[j] = c[i][1] - 1
    elif i != 0:
        if c[i][0] != c[i - 1][0]:
            j += 1
            p[j] = c[i][0]
            q[j] = c[i][1] - 1
            if q[j - 1] < p[j]:
                count += 1
            else:
                if p[j] < p[j - 1]:
                    p[j] = p[j - 1]
                if q[j] > q[j - 1]:
                    q[j] = q[j - 1]
count += 1
print(count)

Solution (Python):
n, m = map(int, input().split(" "))
ab = [list(map(int, input().split(" "))) for _ in range(m)]

ab.sort(key=lambda x: x[1])

count = 0
before = 0
for a_i, b_i in ab:
	if before > a_i:
		continue
	before = b_i
	count += 1

print(count)

Solution (Python):
def main():
    N, M = map(int, input().split())
    A = [tuple(map(int, input().split())) for _ in range(M)]
    S = sorted(A, key=lambda x: x[1])
    count = 0
    last = 0
    for s in S:
        if last < s[0]:
            count += 1
            last = s[1] - 1
    print(count)


if __name__ == "__main__":
    main()

Solution (Python):
N,M=map(int,input().split())
War=[[int(i) for i in input().split()] for i in range(M)]
War.sort(key=lambda x:x[1])

cut=0
ans=0
for i in range(M):
  if War[i][0]>=cut:
    ans+=1
    cut=War[i][1]
print(ans)

Solution (Python):
n,m = map(int,input().split())
connections = sorted([list(map(int,input().split())) for _ in range(m)], key = lambda x: x[1])

cut = 0
ans = 0
for i in range(m):
    if connections[i][0] >= cut:
        ans += 1
        cut = connections[i][1]

print(ans)

Solution (Python):
n, m = map(int, input().split(" "))
ab = [list(map(int, input().split(" "))) for _ in range(m)]

ab.sort(key=lambda x: x[1])

count = 0
x = 0
for a_i, b_i in ab:
	if a_i <= x < b_i:
		continue
	x = b_i-1
	count += 1

print(count)

Solution (Python):
n, m  = [int(i) for i in input().split()]
ab = []
for i in range(m):
    ab.append([int(i) for i in input().split()])

ab.sort()
op_sum = 1
left = ab[0][0]
right = ab[0][1]

for a, b in ab:
    if right <= a:
        op_sum += 1
        left = a
        right = b
    else:
        left = a
        right = min(right, b)

print(op_sum)

Solution (Python):
N,M = map(int,input().split())
src = [tuple(map(int,input().split())) for i in range(M)]

ans = 0
cut = -1
src.sort(key=lambda x:x[1])
for a,b in src:
    if a < cut: continue
    cut = b
    ans += 1
print(ans)

Solution (Python):
import sys
stdin = sys.stdin

sys.setrecursionlimit(10**5)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

n,m = li()
ab = []
for _ in range(m):
    a,b = li_()
    ab.append(tuple([a,b]))
    
ab.sort(key=lambda x:x[1])
ans = 0
cur = -1

for a,b in ab:
    if a >= cur:
        ans += 1
        cur = b
        
print(ans)

Solution (Python):
N,M = map(int,input().split())

claims = []
for i in range(M):
  claims.append(list(map(int,input().split())))
  
claims.sort()

killed = 0
last_killed = [-1,-1]
for claim in claims:
  if (last_killed[1] < claim[0] or last_killed[0] >= claim[1]):
    last_killed = [claim[0],claim[1] -1]
    killed += 1
  last_killed = [max(last_killed[0],claim[0]),min(last_killed[1],claim[1] -1)]
print(killed)

Solution (Python):
N, M = map(int, input().split())
dem = [[0, 0] for i in range(M)]
for i in range(M):
    dem[i][0], dem[i][1] = map(int, input().split())
dem.sort(key=lambda x: (x[1]))
br_flag = [False for i in range(N-1)]
count = 0
a = 0
for i in range(M):
    if a < dem[i][0]:
        br_flag[dem[i][1]-2] = True
        a = dem[i][1] - 1
        count += 1
print(count)

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

Solution (Python):
n,m=map(int,input().split())

data=[10**5+1]*(n+1)
for _ in range(m):
    l,r=map(int,input().split())
    if(r < data[l]):
        data[l]=r
    

ans=1
i=1
tmpr=data[1]
while(1):
    i+=1
    if(n<i):
        break
    if(data[i] < tmpr):
        tmpr=data[i]
    if(tmpr <= i):
        if(data[i]!=10**5+1):
            ans+=1
            tmpr=data[i]

print(ans)

Solution (Python):

n_island, n_demand = map(int, input().split())


demand_list = [list(map(int, input().split())) for i in range(n_demand)]


demand_list = sorted(demand_list, key=(lambda x:x[1]))


b_0 = 0 
count = 0
for i in range(n_demand):
    
    if demand_list[i][0] >= b_0:
        
        count += 1
        b_0 = demand_list[i][1]


print(count)

Solution (Python):
N,M=map(int,input().split())
AB=[]
for _ in range(M):
    AB.append(tuple(map(int,input().split())))
    
request_max=0
request_num=0

AB.sort(key=lambda x:x[1])
for (a,b) in AB:
    if a>=request_max:
        request_num +=1
        request_max = b
print(request_num)

Solution (Python):
import sys

N, M = map(int, input().split())
ab = [list(map(int, line.split())) for line in sys.stdin.readlines()]
ab.sort(key = lambda x : x[1])

ans = 0
last = -1
for a, b in ab:
    if a < last:
        continue
    else:
        ans += 1
        last = b

print(ans)

Solution (Python):
import sys

N, M = map(int, input().split())
ab = [tuple(map(int, line.split())) for line in sys.stdin.readlines()]
ab.sort(key = lambda x : x[1])

ans = 0
last = -1
for a, b in ab:
    if a < last:
        continue
    else:
        ans += 1
        last = b

print(ans)

Solution (Python):
import sys

N, M = map(int, input().split())
ab = [tuple(map(int, sys.stdin.readline().split())) for _ in range(M)]
ab.sort(key = lambda x : x[1])

ans = 0
last = -1
for a, b in ab:
    if a < last:
        continue
    else:
        ans += 1
        last = b

print(ans)

Solution (Python):
N, M = map(int, input().split())
ab = [tuple(map(int, input().split())) for _ in range(M)]
ab.sort(key = lambda x : x[1])

ans = 0
last = -1
for a, b in ab:
    if a < last:
        continue
    else:
        ans += 1
        last = b

print(ans)

Solution (Python):
N, M = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(M)]
ab.sort(key = lambda x : x[1])

ans = 0
last = -1
for a, b in ab:
    if a < last:
        continue
    else:
        ans += 1
        last = b

print(ans)

Solution (Python):
N, M = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(M)]
ab.sort(key = lambda x : x[1])

ans = 0
last = -1
for abTemp in ab:
    if abTemp[0] < last:
        continue
    else:
        ans += 1
        last = abTemp[1]

print(ans)

Solution (Python):
n, m = map(int, input().split())
hope = []
for i in range(m):
    hope.append(list(map(int, input().split())))
    
hope.sort(key=lambda x:x[1])

last = 100000000
count = 0
for i in hope:
    if(i[0]<=last<i[1]):
        continue
    else:
        last = i[1]-1
        count += 1
        
print(count)

Solution (Python):
import numpy as np
N, M = map(int, input().split())
a = np.zeros([M], dtype=int)
b = np.zeros([M], dtype=int)
for i in range(M):
    a[i], b[i] = map(int, input().split())
idx = np.argsort(b)
a = a[idx]
b = b[idx]
c = b[0] - 1
ans = 1
for i in range(1, M):
    if a[i] <= c:
        continue
    else:
        c = b[i] - 1
        ans += 1
print(ans)

Solution (Python):
_, M = map(int, raw_input().split())
lst = []

for i in range(M):
    a, b = map(int, raw_input().split())
    lst.append((b, a))

lst.sort()
pos = 0
ans = 0

for p in lst:
    if p[1] >= pos:
        ans += 1
        pos = p[0]

print ans

Solution (Python):
N, M = map(int,input().split())
m=[list(map(int, input().split()))[::-1] for _ in range(M)]
m.sort()

b=[]
for i in m:
    if len([tmp for tmp in b if tmp>=i[1]])==0:
        b.append(i[0]-1)
print(len(b))

Solution (Python):
islands = []
bridges = []

N, M = map(int, input().split())

for i in range(M):
    a, b = map(int, input().split())
    islands.append({'a': a, 'b': b})

islands.sort(key=lambda x: x['b'])


for i in islands:
    b = [j for j in bridges if j >= i['a']]
    if len(b) == 0:
        bridges.append(i['b'] - 1)


print(len(bridges))

Solution (Python):
from operator import itemgetter

N,M=map(int,input().split())
ab=[[int(i) for i in input().split()] for j in range(M)]
ab=sorted(ab, key=itemgetter(1))
ans=0
k=0
for i in ab:
    if i[0]>k:
        k=i[1]-1
        ans+=1
print(ans)

Solution (Python):
N, M = map(int, input().split())
X = sorted([list(map(int, input().split())) for i in range(M)], key=lambda x: x[1])

r = 0  
ans = 0
for a, b in X:
    if r < a:
        r = b - 1
        ans += 1
        
print(ans)

Solution (Python):

n,m = map(int,input().split())
ab = [list(map(int,input().split())) for _ in range(m)]
x = 0
ab.sort(key = lambda x:x[1])
ans = 0
for a,b in ab:
  if x <= a:
    ans += 1
    x = b
print(ans)

Solution (Python):
N, M = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(M)]
x = 0
ab.sort(key=lambda x: x[1])
ans = 0
for a, b in ab:
    if x <= a:
        ans += 1
        x = b
print(ans)

Solution (Python):
N,M = [int(i) for i in input().split()]
d = []
for i in range(M):
    d.append(list(map(int, input().split())))
d = sorted(d, key=lambda x: x[0])
X=[-2,-1]
D = 0
for i in range(M):
    if X[0] < d[i][1] and d[i][0] < X[1]:
        X = [d[i][0],min(X[1],d[i][1])]
    else:
        D += 1
        X = d[i]
print(D)

Solution (Python):
def m():
    n, m = map(int, input().split())
    bridge = [1 for _ in range(n)]
    g = []
    for _ in range(m):
        a, b = map(int, input().split())
        g.append((a, b))
    g.sort(key=lambda x: x[1])
    cnt = 0
    for e in g:
        f = 0
        for j in range(e[1]-1, e[0]-1, -1):
            if bridge[j] == 0:
                f = 1
                break
        if f:
            continue
        
        
        bridge[e[1]-1] = 0
        cnt += 1
    return cnt

print(m())

Solution (Python):

from operator import itemgetter

n,m = map(int, input().split())
ab = []
for _ in range(m):
    line = list(map(int, input().split()))
    ab.append(line)

ab = sorted(ab, key=itemgetter(1))

cnt = 1
bridge = ab[0][1]-1
for i in range(1,m):
    if ab[i][0]<=bridge and bridge<ab[i][1]:
        continue
    else:
        cnt += 1
        bridge = ab[i][1]-1
print(cnt)

Solution (Python):
n, m = map(int, input().split())
X = list(sorted([list(map(int, input().split())) for _ in range(m)], key=lambda x: x[1]))

elmd = -1
ans = 0
for a, b in X:
    if a <= elmd < b:
        pass
    else:
        elmd = b - 1
        ans += 1

print(ans)

Solution (Python):
N, M = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(M)]

def islands_war(AB):
    AB.sort(key=lambda x: x[1])
    ans = 1
    bridge = AB[0][1] - 1
    for ab in AB:
        if bridge < ab[0]:
            bridge = ab[1] - 1
            ans += 1
    return ans

ans = islands_war(AB)
print(ans)

Solution (Python):
N, M = list(map(int,input().split()))

ans=0
st = [[] for _ in range(N+1)]
goal = [0 for _ in range(N+1)]

for _ in range(M):
    a,b = list(map(int,input().split()))
    st[a] += [b]
    goal[b] += 1

stack = []
for i in range(1,N+1):
    if goal[i]>0:
        ans+=1
        for x in stack:
            goal[x] -= 1
        stack=[]
    if len(st[i])>0:
        stack += st[i]

print(ans)

Solution (Python):
N,M=map(int,input().split())
invs = []
for _ in range(M):
    L,R = map(int,input().split())
    invs.append((L,R-1)) 
invs.sort(key=lambda inv: inv[0])
x = N
ans = 0

for (a,b) in invs:
    if a > x:
        ans += 1
        
        x = b
    else:
        x = min(x,b)

ans += 1

print(ans)

Solution (Python):


N, M = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(M)]

ab.sort(key=lambda x: x[1])

ans = 1
bridge = ab[0][1] - 1

for pair in ab:
    if bridge < pair[0]:
        bridge = pair[1] - 1
        ans += 1

print(ans)

Solution (Python):


N, M = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(M)]

ab.sort(key=lambda x: x[1])

ans = 1
bridge = ab[0][1] - 1

for pair in ab:
    if bridge < pair[0]:
        bridge = pair[1] - 1
        ans += 1

print(ans)

Solution (Python):
il = lambda: list(map(int, input().split()))
ils = lambda n, s="int(input())": [eval(s) for _ in range(n)]

n, m = il()
l = ils(m, "il()")
l.sort(key=lambda x: x[1])
ans = 0
cur = 0
for i in range(m):
    if l[i][0] >= cur:
        cur = l[i][1]
        ans += 1
print(ans)

Solution (Python):
n,m = map(int,input().split(" "))

ab_array = []

for i in range(m):
    ab = list(map(int,input().split(" ")))
    ab_array.append(ab)

ab_array = sorted(ab_array, key = lambda x:x[1])

ans = [ab_array[0][1]]

for i in ab_array:
    if not i[0] < ans[-1] <=i[1]:
        ans.append(i[1])
print(len(ans))

Solution (Python):

"""
D - Islands War
https://beta.atcoder.jp/contests/abc103/tasks/abc103_d

"""
import sys
from sys import stdin
input = stdin.readline


def solve(N, M, data):
    ans = 0
    data.sort(key=lambda x: x[1])
    removed = -1
    for a, b in data:
        if not a <= removed < b:
            ans += 1
            removed = b - 1
    return ans


def main(args):
    N, M = map(int, input().split())
    data = [list(map(int, input().split())) for _ in range(M)]
    ans = solve(N, M, data)
    print(ans)


if __name__ == '__main__':
    main(sys.argv[1:])

Solution (Python):
n, m = map(int, input().split())

ab = []

for i in range(m):
    ab.append(tuple(map(int, input().split())))

ab.sort(reverse = True)

ans = 0
last = n

for elm in ab:
    a = elm[0]
    b = elm[1]
    if b <= last:
        ans += 1
        last = a

print(ans)

Solution (Python):
def main():
	n, m = list(map(int, input().split()))
	rqs = [list(map(int, input().split())) for _ in range(m)]

	rqs.sort(key = lambda x: x[1])

	b = -1
	cnt = 0
	
	for x in rqs:
		if b < x[0]:
			b = x[1] - 1
			cnt += 1

	print(cnt)

if __name__ == '__main__':
	main()

Solution (Python):
n, m = map(int, input().split())
rec = []
for i in range(m):
    a, b = map(int, input().split())
    rec.append((a, b))

rec = sorted(rec, key=lambda s: s[1])
pre = -1
num = 0
for x, y in rec:
    if pre == -1:
        pre = y - 1
        num += 1
    elif x <= pre:
        continue
    else:
        pre = y - 1
        num += 1

print(num)

Solution (Python):
N, M = map(int, input().split())
AB = []
for i in range(M):
    a, b = map(int, input().split())
    AB.append([b, a])
AB.sort()
for i in range(M):
    if i == 0:
       j = AB[i][0] - 1
       ans = 1
    else:
        if AB[i][1] <= j and j < AB[i][0]:
            1
        else:
            j = AB[i][0] - 1
            ans += 1

print(ans)

Solution (Python):
N,M=map(int, input().split())
AB=list(sorted([list(map(int, input().split())) for _ in range(M)], key=lambda x :x[1]))
ans=1
A=[AB[0]]
for i in range(1,M):
    if AB[i][0]>=A[-1][1]:
        ans+=1
        A.append(AB[i])
print(ans)

Solution (Python):
m = lambda: map(int,input().split())
N,M = m()
l = [tuple(m()) for _ in range(M)]
ans = []
l.sort(key=lambda x: x[1])
for i in range(M):
    if not ans or ans[-1]<l[i][0]:
        ans.append(l[i][1]-1)
print(len(ans))

Solution (Python):

N, M = map(int, input().split())
ab = [list(map(int, input().split())) for i in range(M)]


max_as = [0] * N
for a, b in ab:
    if max_as[b - 1] < a: max_as[b - 1] = a


ans = 0
last_bridge = -1
for bm, max_a in enumerate(max_as):
    if max_a < 1: continue
    elif max_a <= last_bridge: continue
    ans += 1
    last_bridge = bm
        






















print(ans)

Solution (Python):
n,m = map(int, input().split())
ab = [tuple(map(int, input().split())) for _ in range(m)]
ab.sort(key=lambda tup: tup[1])
bridge,ans=-1, 0
for a,b in ab:
    if a <= bridge:
        continue
    else:
        bridge = b - 1
        ans += 1
print(ans)

Solution (Python):
N,M = map(int,input().split(" "))
pair = []
for i in range(M):
    a,b = map(int,input().split(" "))
    pair.append((a,b))
pair.sort(key=lambda x:x[1])

cur = (-1)
cnt = 0
for i in range(M):
    if pair[i][0] <= cur and cur < pair[i][1]:
        pass
    else:
        cur = pair[i][1] - 1
        cnt += 1

print(cnt)

Solution (Python):
n, m = map(int, input().split())
ab = []
for i in range(m):
    a, b = map(int, input().split())
    ab.append((i, a, b))

rm = []
for i, a, b in sorted(ab, key=lambda x:x[2]):
    pre = ab[rm[-1]][2] - 1 if len(rm) else 0
    if a <= pre:
        continue
    else:
        rm.append(i)
print(len(rm))

Solution (Python):
from pprint import pprint
n, m = map(int, input().split())
ab = []
for i in range(m):
    a, b = map(int, input().split())
    ab.append((i, a, b))

rm = []
for i, a, b in sorted(ab, key=lambda x:x[2]):
    pre = ab[rm[-1]][2] - 1 if len(rm) else 0
    if a <= pre:
        continue
    else:
        rm.append(i)
print(len(rm))

Solution (Python):
n,m=map(int,input().split())
l=[list(map(int,input().split())) for _ in range(m)]
l.sort(key=lambda x : x[1])
a=0
b=0
for x in l:
  if x[0]>=b:
    b=x[1]
    a+=1
print(a)

Solution (Python):
N, M = map(int,input().split())
shima = [list(map(int,input().split())) for k in range(M)]
shima = sorted(shima, key = lambda x: x[1])

now = 0
ans = 0
for i in shima:
    if now < i[0]:
        now = i[1]-1
        ans += 1
print(ans)

Solution (Python):
N, M = map(int, input().split())
E = []
for i in range(M):
    a, b = map(int, input().split())
    a, b = a - 1, b - 1
    E.append([a, b])

E.sort(key=lambda x: x[1])

r = 0
ans = 0
for a, b in E:
    if a >= r:
        ans += 1
        r = b

print(ans)

Solution (Python):
N, M = map(int, input().split())
ab = []
for _ in range(M):
    ab.append(tuple(map(int, input().split())))
ab.sort()
r = 0
ans = 0
for a, b in ab:
    if a >= r:
        r = b
        ans += 1
    else:
        r = min(b, r)
print(ans)

Solution (Python):
from operator import itemgetter

N, M = map(int, input().split(" "))
A = []
cnt = 0
for i in range(M):
    A.append(list(map(int, input().split(" "))))

A = sorted(A, key=itemgetter(1))

endtime = 0
for i in range(M):
    if A[i][0] >= endtime:
        endtime = A[i][1]
        cnt += 1
print(cnt)

Solution (Python):
N, M = map(int, input().split())
req = [list(map(int, input().split())) for i in range(M)]
req.sort()
ans = 0
left = 0
right = 0
for i in range(M):
    if req[i][0] >= right:
        ans += 1
        left, right = req[i][0], req[i][1]
    else:
        left = req[i][0]
        right = min(req[i][1], right)
 
print(ans)

Solution (Python):
N, M = map(int, input().split())
req = [list(map(int, input().split())) for i in range(M)]
req.sort(key = lambda x:(x[0], -x[1]))
ans = 0
left = 0
right = 0
for i in range(M):
    if req[i][0] >= right:
        ans += 1
        left, right = req[i][0], req[i][1]
    else:
        left = req[i][0]
        right = min(req[i][1], right)

print(ans)

Solution (Python):
N, M = map(int, input().split())
req = [list(map(int, input().split())) for i in range(M)]
req.sort(key = lambda x:x[1])
last_destroyed = 0
ans = 0
for i in range(M):
    if req[i][0] >= last_destroyed :
        ans += 1
        last_destroyed = req[i][1]
print(ans)

Solution (Python):
N,M=map(int,input().split())
requires=[]
for i in range(M):
    requires.append(list(map(int,input().split())))
sorted_requires=sorted(requires,key=lambda x:x[1])

broken_bridges=[0]
for sorted_require in sorted_requires:
    if max(broken_bridges) >sorted_require[0]:
        continue
    else:
        broken_bridges.append(sorted_require[1])

ans=len(broken_bridges)-1
print(ans)

Solution (Python):
import numpy as np

N, M = map(int, input().split())

D = []
dic = dict()

for m in range(M):
    a, b = map(int, input().split())
    D.append((b, a))
    if b in dic.keys() and (dic[b] > a):
        continue
    else:
        dic[b] = a
    


dp = np.zeros(N+1, dtype=int)

dp[0] = 0
for i in range(1, N+1):
    dp[i] = dp[i-1]
    if i in dic.keys():
        a = dic[i]
        if dp[a] == dp[i]:
            dp[i] = dp[i] + 1


print(dp[N])

Solution (Python):
n,m = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(m)]
ab.sort(key=lambda x:x[1])
cnt = 0
end_time = 0
for a,b in ab:
  if end_time <= a:
    end_time = b
    cnt += 1
print(cnt)

Solution (Python):
n,m=list(map(int,input().split()))
c=[]
for i in range(m):
    a,b=list(map(int,input().split()))
    d=[]
    d.append(a)
    d.append(b)
    c.append(d)
c.sort(key=lambda x: x[1])

cur=0
ans=0
for i in range(m):
    if c[i][0] >= cur:
        cur = c[i][1]
        ans += 1  
print(ans)

Solution (Python):


def getG(N, M):
    G=[list() for i in range(N)]
    for i in range(M):
        a,b=map(int,input().split())
        a-=1
        b-=1
        G[a].append(b)
        G[b].append(a)

    return G

def solve(G, N):
    ans = 0
    index = -1

    for i in range(1, N):
        for p in G[i]:
            if index < p < i:
                ans += 1
                index = i - 1
    return ans

if __name__ == "__main__":
    N, M = map(int, input().split())
    G = getG(N, M)
    print(solve(G, N))

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    n,m = LI()
    e = sorted([LI()[::-1] for _ in range(m)])
    r = 0
    c = -2
    for b,a in e:
        if a > c:
            r += 1
            c = b - 0.5
    return r


print(main())

Solution (Python):

n, m = map(int, input().split())
d = []
for i in range(m):
    a, b = map(int, input().split())
    d.append([a, b])

d.sort(key=lambda x: (x[0], x[1]))

mn = 100000000
ans = 0
for a, b in d:
    if a >= mn:
        ans += 1
        mn = b
    mn = min(mn, b)

if mn != 100000000:
    ans += 1
print(ans)

Solution (Python):

"""
Created on Thu Aug  9 04:30:54 2018

@author: Yuki
"""
import numpy as np
N, M = map(int, input().split())
AB = np.zeros([M, 2])
for i in range(M):
    AB[i, 0], AB[i, 1] = map(int, input().split())

AB = AB[np.argsort(AB[:, 1])]

cut_br = [AB[0, 1]-1]
for i in range(1, M):
    flag = False
    if AB[i, 0] <= cut_br[-1]:
        if cut_br[-1] < AB[i, 1]:
            flag = True
    if not(flag):
        cut_br.append(AB[i, 1]-1)

print(len(cut_br))

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

Solution (Python):
n, m = [int(i) for i in input().split()]
A = [[int(i) for i in input().split()] for j in range(m)]

A.sort(key=lambda a:a[1])
ans = 0
last = 0

for a, b in A:
    if a >= last:
        ans += 1
        last = b

print(ans)

Solution (Python):
n, m = [int(i) for i in input().split()]
A = [[int(i) for i in input().split()] for j in range(m)]

A.sort(key=lambda a:a[1])
ans = 0
i = 0

while i < m:
    b = A[i][1]
    ans += 1
    i += 1
    while i < m:
        if A[i][0] >= b:
            break
        i += 1

print(ans)

Solution (Python):
N,M = map(int,input().split())
ab = []
pre = 0
ans = 0
for _ in range(M):
    a,b = map(int,input().split())
    ab.append([a-1,b-1])
ab = sorted(ab, key=lambda x: x[1])
for i in ab:
    if i[0] >= pre:
        ans +=1
        pre = i[1]
print(ans)

Solution (Python):

from operator import itemgetter
 
n,m=map(int, input().split())
A=[]
B=[]
a=0
b=0
for i in range(m):
  a,b=map(int, input().split())
  A.append([a,b])

A.sort(key=itemgetter(1))
bri=0 

count=0

for i in range(m):
  a=A[i][0]
  b=A[i][1]
  
  if a>=bri:
    bri=b
    count+=1

print(count)

Solution (Python):
n, m = map(int, input().split())

x = [[0, 0] for i in range(m)]
for i in range(m):
    x[i][0], x[i][1] = map(int, input().split())
x = sorted(x, key=lambda y: y[0])
ans = 1
mx = max([x[i][0] for i in range(m)])
while len(x) > 0:
    for i in range(len(x)-1, -1, -1):
        if mx < x[i][1]:
            x.pop(i)
            break
        else:
            mx = x[i][0]
            ans += 1
            break
print(ans)

Solution (Python):
N, M = map(int, input().split())
l = [list(map(int, input().split())) for i in range(M)]
l = sorted(l, key = lambda l:(l[1]))

p_num = -1
ans = 0

for i in range(M):
	if not l[i][0] <= p_num:
		p_num = l[i][1] - 1
		ans += 1

print(ans)

Solution (Python):
break_offs = set()
N, M = map(int, input().split())
for i in range(M):
    a, b = map(int, input().split())
    if a > b:
        a, b = b, a
    break_offs.add((a, b))

last_bridge = 0
count = 0
for a, b in sorted(list(break_offs), key=lambda x:x[1]):
    if last_bridge <= a:
        last_bridge = b
        count += 1

print(count)