소프티어

강의실 배정문제 반례 찾아주시면 감사하겠습니다(python)

import sys input = sys.stdin.readline n = int(input().strip()) time_list = [] for _ in range(n): time_list.append(list(map(int, input().split()))) time_list.sort(key=lambda x: (x[0], x[1])) count = 0 end = 0 for t in time_list: if t[0] >= end: count += 1 end = t[1] print(count) 반례 찾아주시면 감사하겠습니다. 시간 초과는 아슬아슬하게 안쪽으로 들어오는데 로직에 어떤부분이 잘못되었는지 모르겠어요..

len으로 답 리턴했을 때 오답 문의

import sys N = int(input()) lec = [] max_lec = [] for i in range(N) : lec.append(list(map(int,sys.stdin.readline().split()))) lec = sorted(lec,key = lambda x : (x[1] ,x[0])) end_time = 0 max_lec.append(lec[0]) #counter = 1 end_time = lec[0][1] for i in range(1,N): if lec[i][0] < end_time : continue elif lec[i][0] >= end_time : max_lec.append(lec[i]) #counter += 1 end_time = lec[i][1] print(len(max_lec)) #print(counter) 조건을 만족할 때 마다 배열의 요소를 추가해서 그 길이를 답으로 리턴하는 것으로 했을 때, 테스트 케이스 2개가 오류가 났는데, 이 ...

틀린 부분을 알려주세요

테스트 케이스 중 하나만 오답이라고 나오는데 어느 부분 때문에 틀린 건지 모르겠습니다 ㅜㅜ 강의가 끝나는 시간을 기준으로 오름차순 정렬한 후에, 가장 첫 번째 요소부터 끝까지 돌면서 이전 강의의 끝나는 시간보다 지금 강의의 시작 시간이 크거나 같으면 ArrayList에 추가하는 식으로 진행했습니다. import java.io.*; import java.util.*; public class Main {     public static void main(String[] args) {         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));         int N;         Class[] arr;         int[] dp;                  try{                          N = Integer.parseInt(br....

이거 타임아웃같은데 뭐가문제일까요?

import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int N = Integer.parseInt(br.readLine()); int arr[][] = new int[N][2]; for(int i =0; i<N; i++){ StringTokenizer st = new StringTokenizer(br.readLine()); arr[i][0] = Integer.parseInt(st.nextToken()); arr[i][1] = Integer.parseIn...

강의실 배정 - 시간 초과 문제

강의실 배정문제에서 sort() <--- 시간 초과가 인하여 실패하는데 내용을 찾아보니 python에서는 heapq 모듈을 이용해서 구현하던데 js에서 heap 을 구현해서 작성해야 할까요? 다른 방법은 없을까요? const fs = require('fs'); const args = fs.readFileSync('/dev/stdin').toString().trim().split(' '); let [n, ...times] = args; const arr = times.map(i=> i.split(' ').map(j=> +j)); arr.sort((a,b) => { if (a[1] === b[1]) return a[0] - b[0]; else return a[1] - b[1]; }) let answer = 0; let endPoint = 0; for (let i=0; i

강의실 배정 python 시간 초과 질문입니다2

이전 질문 링크: Softeer 최소힙을 사용하여 문제를 해결하였습니다. 그런데 1) 한번에 heapify (O(n))진행 후, 하나 씩 heappop(O(nlogn))을 하는 경우(전체 O(nlogn))에는 시간초과가 발생하고 2) 하나 씩 heappush (O(nlogn))진행 후, 하나 씩 heappop(O(nlogn))을 하는 경우(전체 O(nlogn))에는 통과합니다. 일반적으로 힙정렬이 다른 정렬에 비해 일반적으로 느린 편으로 알고 있고, 1)의 경우에도 Tim sort를 진행한 경우보다 느린 것을 확인 할 수 있었습니다. 2)의 경우가 1)과 Tim sort보다 빠르게 진행되는 이유가 궁금합니다. (n의 크기가 충분히 크지 않아 상수 C의 차이가 더 중요한 것일지도 모릅니다. (실제 동작시간: Cnlogn+a)) 추가적으로 1),2), list.sort()(Timsort) 세 가지 풀이 모두 시간 복잡도는 O(nlogn)으로 동일합니다. 문제의 의도가 같은 로직이라...

강의실 배정 python 시간 초과 질문입니다

Python으로 아래와 같이 코드를 작성하였는데, 시간 초과가 발생합니다. 최대 시간이 걸린 케이스 기준으로 입력값(input)을 받아오는데 600ms 정도가 걸렸고, 내장함수 list.sort()를 이용한 정렬을 마치면 총 2090ms 가량이 소요되어 시간 초과가 발생합니다. 알골선생 풀이(링크: Softeer) 역시 같은 로직으로, 종료 시간을 기준으로 정렬 후 강의실을 배정하여 O(nlogn)의 시간복잡도를 가지는데 시간 초과가 왜 발생하는지 모르겠습니다. 1) 내장함수인 list.sort()에서 사용되는 Tim sort는 일반적인 경우에 빠르며 배열이 완전 무작위인 최악의 경우에도 시간복잡도가 O(nlogn)인 것으로 알고 있고 있는데, Python으로 이 문제를 해결할 수 있는 다른 정렬 방법이나 알고리즘이 있는 것인지 궁금합니다. 2) 최대 입력값을 고려해보면 필요 연산이 C*106 *log106 정도로 대략 C *20,000,000(C*2000만) 정도로 예상되는데...

강의실 배정 문제 시간초과 관련

시간 복잡도 측면에서는 크게 개선할 여지가 보이지 않는데요, 왜 TimeOut이 뜨는건지, 시간 제약사항이 적절한건지 확인 요청드립니다. import java.util.*; import java.io.*; class Cls{ int start; int end; public Cls(int s, int e){ start=s; end=e; } } public class Main { public static void main(String args[]) { Scanner sc=new Scanner(System.in); int N=sc.nextInt(); List schd=new ArrayList<>(); for(int i=0;ic1.end-c2.end); Cls curCls=null; int c...

강의실 배정 performance 한개 코드는 정답 다른 하나는 오답(java)

정답 코드 import java.util.*; import java.io.*; public class Main { static class Data { int start; int end; public Data(int start, int end) { this.start = start; this.end = end; } } public static void main(String[] args) throws NumberFormatException, IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int num = Integer.parseInt(br.readLine()); ArrayList list = new ArrayList<>(); for (int i = 0; i < num; i++) { ...

강의실 배정 질문드립니다.

import sys from random import * from collections import deque input_first = list(map(int,sys.stdin.readline().split())) # [3] n = input_first[0] # # int 값 : 3 s_f_list = [] for i in range(0, n): # 데이터 입력 받아서 2차원 리스트에 저장 s, f = list(map(int,sys.stdin.readline().split())) s_f_list.append([s, f]) s_f_list.sort(key=lambda x:x[1]) # 2차원 리스트의 [1]번째 값으로 정렬 # print(s_f_list, type(s_f_list)) # [[1,3], [2,4], [3,5]] # s_f_list = deque(s_f_list) # print(s_f_list, type(s_...