Problem:

Activity Selection Problem

There are $n$ acitivities with start times $\{s_i\}$ and finish times $\{t_i\}$. Assuming that a person can only work on a single activity at a time, find the maximum number of activities that can be performed by a single person.

Input

$n$
$s_1$ $t_1$
$s_2$ $t_2$
:
$s_n$ $t_n$

The first line consists of the integer $n$. In the following $n$ lines, the start time $s_i$ and the finish time $t_i$ of the activity $i$ are given.

出力

Print the maximum number of activities in a line.

Constraints

  
$1 \le n \le 10^5$

  
$1 \le s_i \lt t_i \le 10^9 (1 \le i \le n)$

Sample Input 1

5
1 2
3 9
3 5
5 9
6 8

Sample Output 1

3

Sample Input 2

3
1 5
3 4
2 5

Sample Output 2

1

Sample Input 3

3
1 2
2 3
3 4

Sample Output 3

2



Sample input:
5
1 2
3 9
3 5
5 9
6 8


Sample output:
3

Submission status: Wrong Answer

Solution code:
class Activity:
	def __init__(self,s,e):
		self.s=s
		self.e=e
		self.k=str(s)+'-'+str(e)

n=int(input())
acts=[]
for i in range(n):
	si,ei=map(int,input().split())
	acts.append(Activity(si,ei))
	
acts.sort(key=lambda x:x.k)
stack=[]
stack.append(acts[0])

for i in range(1,n):
	last = stack[-1]
	acti = acts[i]
	if acti.s > last.e:
		stack.append(acti)
	elif acti.e < last.e:
		stack.pop()
		stack.append(acti)

print(len(stack))

Submission status: Wrong Answer

Solution code:
class Activity:
	def __init__(self,s,e):
		self.s=s
		self.e=e
		self.k=str(s)+'-'+str(e)

n=int(input())
acts=[]
for i in range(n):
	si,ei=map(int,input().split())
	acts.append(Activity(si,ei))
	
acts.sort(key=lambda x:x.k)
stack=[]
stack.append(acts[0])

for i in range(1,n):
	last = stack[0]
	acti = acts[i]
	if acti.s > last.e:
		stack.append(acti)
	elif acti.e < last.e:
		stack.pop()
		stack.append(acti)

print(len(stack))

Submission status: Wrong Answer

Solution code:
n = int(input())
data = []
for _ in range(n):
    x,y = map(int,input().split(" "))
    data.append([x,y])

data.sort()
maxa = sorted(data, key=lambda x:x[1])[-1][1]

index = 0
count = 0
while True:
    taisyo = []
    for ele in data:
        if ele[0] == index:
            taisyo.append(ele)
    if taisyo == []:
        index += 1
    else:
        lmao = sorted(taisyo, key=lambda x:x[1])
        index = lmao[0][1] + 1
        count += 1
    if index > maxa:
        break

print(count)

Submission status: Accepted

Solution code:
class Activity:
	def __init__(self,s,e):
		self.s=s
		self.e=e

n=int(input())
acts=[]
for i in range(n):
	si,ei=map(int,input().split())
	acts.append(Activity(si,ei))
	
acts.sort(key=lambda x:x.s)
stack=[]
stack.append(acts[0])

for i in range(1,n):
	last = stack[-1]
	acti = acts[i]
	if acti.s > last.e:
		stack.append(acti)
	elif acti.e < last.e:
		stack.pop()
		stack.append(acti)
print(len(stack))

Submission status: Accepted

Solution code:
n = int(input())
lst = [list(map(int, input().split())) for _ in range(n)]
lst.sort(key=lambda x:x[1])
now = -1
ans = 0
for s, t in lst:
  if now < s:
    ans += 1
    now = t
print(ans)

Submission status: Accepted

Solution code:
# https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/15/ALDS1_15_C

n = int(input())
lst = [list(map(int, input().split())) for _ in range(n)]
lst.sort(key=lambda x: x[1])
now = -1
ans = 0
for s, t in lst:
    if now < s:
        ans += 1
        now = t
print(ans)

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
N = int(input())
que = []
P = [list(map(int, input().split())) for i in range(N)]
P.sort()
ans = 0
for s, t in P:
    while que and que[0][0] < s:
        ans = max(ans, heappop(que)[1])
    heappush(que, (t, ans+1))
while que:
    ans = max(ans, heappop(que)[1])
print(ans)

Submission status: Accepted

Solution code:
import heapq

n = int(input())
hq = []
for _ in range(n):
    start, end = map(int, input().split())
    heapq.heappush(hq, (end, start))

ans = 0
time = 0
while len(hq) > 0:
    end, start = heapq.heappop(hq)
    if time < start:
        time = end
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
n = int(input())

lst = [list(map(int, input().split())) for _ in range(n)]
lst.sort(key = lambda x:x[1])
now = -1
ans = 0

for s, t in lst:
    if now < s:
        ans += 1
        now = t

print(ans)

Submission status: Accepted

Solution code:
import sys, collections
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = 10**10
def I(): return int(input())
def F(): return float(input())
def SS(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LSS(): return input().split()

def resolve():
    n = I()
    st = [LI() for _ in range(n)]
    # 開始時間が大丈夫で、終了時間の早いものから入れていく
    st.sort(key= lambda x: x[1])

    ans = 0
    end_time = 0
    for i in range(n):
        if st[i][0] > end_time:
            ans += 1
            end_time = st[i][1]

    print(ans)

if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
def act(st):
    st.sort(key = lambda x:x[0])
    OP = [st[0]]

    for i in range(1,len(st)):
        if OP[len(OP)-1][1] < st[i][0]:
            OP.append(st[i])
        elif OP[len(OP)-1][1] <= st[i][1]:
            pass
        else:
            OP.pop()
            OP.append(st[i])
    return len(OP)

def main():
    n = int(input())
    st = [tuple(map(int,input().split())) for _ in range(n)]

    ans = act(st)
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:

def main():
    n = int(input())
    sch = []
    for _ in range(n):
        sch.append(list(map(int,input().split())))
    sch.sort(key=lambda a: a[1])
    res,t = 0,-1
    for i in range(n):
        if t<sch[i][0]:
            t = sch[i][1]
            res+=1
    print (res)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:

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

Submission status: Accepted

Solution code:
n = (int)(input())
list=[]
for i in range(n):
    k = input().split(" ")
    a=(int)(k[0])
    b=(int)(k[1])
    list.append([a,b])
list = sorted(list,key=lambda x: x[1])
count=0
time=0
for i in range(n):
    if(time<list[i][0]):
        count+=1
        time=list[i][1]
print(count)

Submission status: Accepted

Solution code:
n = int(input())
Act = []
maxt= 0
for _ in range(n):
    s,t = map(int,input().split( ))
    Act.append([s,t])
    maxt = max(maxt,t)
#print(*Act)
Act.sort()
last = maxt+1
cnt = 0
for i in range(n-1,-1,-1):
    if Act[i][1] <last:
        cnt += 1
        last = Act[i][0]
        #print(last)
print(cnt)

Submission status: Accepted

Solution code:
import heapq

n = int(raw_input())
A = [map(int,raw_input().split()) for _ in range(n)]
A = sorted(A, key=lambda x:x[1])

ans = 0
m = 0
for s,e in A:
    if m < s:
        ans += 1
        m = e
print ans

Submission status: Accepted

Solution code:
if __name__ == "__main__":
    num_activities = int(input())
    activities = [[0, 0] for _ in range(num_activities)]
    for i in range(num_activities):
        activities[i] = list(map(lambda x: int(x), input().split()))

    # Sort by end time in the ascending order.
    activities = sorted(activities, key=lambda x: x[1])

    current_start = -1
    result = 0
    for start, end in activities:
        if current_start < start:
            result += 1
            current_start = end

    print(result)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Greedy algorithms - Activity Selection Problem
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_15_C&lang=jp

"""
n = int(input())
activities = sorted([[int(i) for i in input().split()] for _ in range(n)], key=lambda x: x[1], reverse=True)

ans, ct = 0, 0
while activities:
    s, t = activities.pop()
    if s > ct:
        ct = t
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
n = int(input())

time = []

for _ in range(n):
    s, t = map(int, input().split())

    time.append((s, t))

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

now = 0
ans = 0
for s, t in time:
    if now < s:
        ans += 1
        now = t

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
A = [[int(i) for i in input().split()] for _ in range(n)]
A.sort(key = lambda x:x[1])
t = 0
ans = 0
for i in A:
    if t < i[0]:
        ans += 1
        t = i[1]
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
t_s = []
for i in range(n):
    a , b = map(int, input().split())
    t_s += [(b, a)]
t_s.sort()
Sum = 1
i = 1
t_now = t_s[0][0]
while i <= n-1:
    for a in t_s[i:]:
        i = i + 1
        if t_now < a[1]:
            Sum += 1
            t_now = a[0]
            
print(Sum)

Submission status: Accepted

Solution code:
n = int(input())
A = []

for i in range(n):
    s, t = [int(x) for x in input().split()]
    A.append((s, t))

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

ans = 0
t = -1

for a in A:
    if a[0] > t:
        ans += 1
        t = a[1]

print(ans)

Submission status: Accepted

Solution code:
readline = open(0).readline
from heapq import heappush, heappop
N = int(readline())
que = []
P = [list(map(int, readline().split())) for i in range(N)]
P.sort()
ans = 0
for s, t in P:
    while que and que[0][0] < s:
        ans = max(ans, heappop(que)[1])
    heappush(que, (t, ans+1))
while que:
    ans = max(ans, heappop(que)[1])
open(1, 'w').write("%d\n" % ans)