Submission #73381428

---

Source Code Expand

import sys
sys.setrecursionlimit(10**7)
# def input(): return sys.stdin.readline()[:-1]

#################################################################
###### COMMENT FIRST THREE LINS FOR CODEFORCES AND ATCODER ######
#################################################################

        
mod = 10**9 + 7
# def readFloat():return float(input())
# def readFloatList():return list(map(float,input().split()))
def read_int():return int(input())
def read_int_list():return list(map(int,input().split()))
def read_string_list():return list(input())
def read_string_list_with_space():return list(input().split())
def read_string():return input()
def read_graph():
    n,m = read_int_list()
    graph = [[] for _ in range(n+1)]
    for _ in range(m):
        u,v = read_int_list()
        graph[u].append(v)
        graph[v].append(u)
    return graph
from collections import defaultdict
import heapq

def dfs(i,vis,cache,g):
    if cache[i] is not None:
        return cache[i]
    if i == g[i]:
        cache[i] = i
        return i
    j = g[i]
    if not vis[j]:
        vis[j] = True
        res = dfs(j,vis,cache,g)
        cache[i] = res
        cache[j] = res
        return res
    else:
        cache[i] = cache[j]
        return cache[j]



def execute():
    n,m = read_int_list()
    a = [read_int_list() for _ in range(m)]
    a.sort(key=lambda x:x[0])
    count= 0
    covered = 0 
    i = 0
    while covered < n :
        best = -1
        while i < m and a[i][0]<= covered+1:
            if a[i][-1] > best:
                best = a[i][-1]
            i += 1
        if best == -1 or best <= covered:
            print("-1")
            return
        
        count += 1
        covered = best
    print(count)






if __name__ == "__main__":
    execute()

Submission Info

Judge Result