A bus route has stops numbered 1 to n in order. The bus runs once from stop 1 to stop n.
The road from stop i to stop i+1 is called stretch i (1 ≤ i ≤ n − 1).
There are m passengers, and each passenger is given by two integers a and b. The passenger boards at stop a and gets off at stop b (a < b).
So the passenger is on the bus for stretches a through b − 1. Even if someone else boards at stop b, the passenger who got off is not on stretch b.
Find the largest number of people on the bus over all stretches.
Also find the smallest and the largest number among the stretches with that largest count. If only one stretch has it, the two numbers are equal.
Print on one line, separated by single spaces, the largest number of people, the smallest stretch number and the largest stretch number.
The first line gives n and m, and each of the next m lines gives a and b for one passenger, separated by a space.
Input
2 ≤ n ≤ 9,999, 1 ≤ m ≤ 10,000, 1 ≤ a < b ≤ n (all integers)
Output
One line: the largest number of people, the smallest and the largest number of a stretch with it
Example 1 · stdin
5 4
1 3
2 5
3 4
4 5
stdout
2 2 4
Example 2 · stdin
4 3
1 2
2 3
3 4
stdout
1 1 3
main.py
Error List00F8 ↓ · ⇧F8 ↑
Input (stdin)
When you run, these lines are fed to input()/stdin in order (the program doesn't stop to ask).
$ Ready
Open this on a computer to write and run code. On mobile you can read the problem and the solutions.
In other languagesShow solutions by language · 8 languages
Adding one to every stretch from a to b − 1 for each passenger is 10,000 passengers × 9,998 stretches, about 100 million steps in the worst case, too slow for Python and Craykon. Use a difference list instead. For each passenger write only diff[a] += 1 and diff[b] -= 1, then add up from stretch 1 forward (a prefix sum); the running value is the number of people on that stretch. Where you subtract is the trap. The passenger gets off at stop b, so subtract from stretch b; subtracting at diff[b + 1] keeps them on the bus one stretch too long. b can be n, so the list needs n + 1 slots. Java new int[n] throws ArrayIndexOutOfBoundsException, C# throws IndexOutOfRangeException, and C silently writes past the array. JS/TS new Array(n + 1) has only empty slots, so += 1 gives NaN; add .fill(0). Python [0] * (n + 1), C++ std::vector<int>(n + 1, 0), Craykon NewList(n + 1, 0) and Java/C# int[] start at 0. To find the first and last stretch in one pass, change the first stretch only when the count gets larger (>), and on equal (==) change only the last stretch.
Pythonmain.py · 20 lines
import sysdata = sys.stdin.buffer.read().split()n, m = int(data[0]), int(data[1])# 차이 목록: a번 구간부터 한 명 늘고, b번 구간부터 한 명 준다(b번 정류장에서 내리니까)diff = [0] * (n + 1)for k in range(m): a, b = int(data[2 + 2 * k]), int(data[3 + 2 * k]) diff[a] += 1 diff[b] -= 1load = 0best, first, last = -1, 0, 0for i in range(1, n): # i번 구간: i번 → i+1번 정류장 load += diff[i] # 앞에서부터 더하면 그 구간에 있는 사람 수 if load > best: best, first, last = load, i, i elif load == best: last = iprint(best, first, last)
JavaScriptmain.js · 15 lines
const nums = require("fs").readFileSync(0, "utf8").trim().split(/\s+/).map(Number);const [n, m] = nums;// fill(0)이 없으면 빈 칸이라 += 1이 NaN이 된다const diff = new Array(n + 1).fill(0);for (let k = 0; k < m; k++) { diff[nums[2 + 2 * k]] += 1; diff[nums[3 + 2 * k]] -= 1;}let load = 0, best = -1, first = 0, last = 0;for (let i = 1; i < n; i++) { load += diff[i]; if (load > best) [best, first, last] = [load, i, i]; else if (load === best) last = i;}console.log(`${best} ${first} ${last}`);
TypeScriptmain.ts · 15 lines
import { readFileSync } from "node:fs";const nums: number[] = readFileSync(0, "utf8").trim().split(/\s+/).map(Number);const [n, m] = nums;const diff: number[] = new Array<number>(n + 1).fill(0);for (let k = 0; k < m; k++) { diff[nums[2 + 2 * k]] += 1; diff[nums[3 + 2 * k]] -= 1;}let load = 0, best = -1, first = 0, last = 0;for (let i = 1; i < n; i++) { load += diff[i]; if (load > best) [best, first, last] = [load, i, i]; else if (load === best) last = i;}console.log(`${best} ${first} ${last}`);
JavaMain.java · 38 lines
import java.io.DataInputStream;import java.io.IOException;public class Main { static DataInputStream in = new DataInputStream(System.in); static int readInt() throws IOException { int c = in.read(); while (c < '0') c = in.read(); int r = 0; while (c >= '0') { r = r * 10 + (c - '0'); c = in.read(); } return r; } public static void main(String[] args) throws IOException { int n = readInt(), m = readInt(); int[] diff = new int[n + 1]; // b는 n까지 오니 n + 1칸 for (int k = 0; k < m; k++) { int a = readInt(), b = readInt(); diff[a]++; diff[b]--; } int load = 0, best = -1, first = 0, last = 0; for (int i = 1; i < n; i++) { load += diff[i]; if (load > best) { best = load; first = last = i; } else if (load == best) { last = i; } } System.out.println(best + " " + first + " " + last); }}
C#Main.cs · 25 lines
using System;using System.IO;class Program{ static void Main() { string[] t = Console.In.ReadToEnd().Split((char[])null, StringSplitOptions.RemoveEmptyEntries); int n = int.Parse(t[0]), m = int.Parse(t[1]); var diff = new int[n + 1]; for (int k = 0; k < m; k++) { diff[int.Parse(t[2 + 2 * k])]++; diff[int.Parse(t[3 + 2 * k])]--; } int load = 0, best = -1, first = 0, last = 0; for (int i = 1; i < n; i++) { load += diff[i]; if (load > best) { best = load; first = last = i; } else if (load == best) last = i; } Console.WriteLine($"{best} {first} {last}"); }}
C++main.cpp · 27 lines
#include <iostream>#include <vector>int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); int n, m; std::cin >> n >> m; std::vector<int> diff(n + 1, 0); for (int k = 0; k < m; k++) { int a, b; std::cin >> a >> b; diff[a]++; diff[b]--; } int load = 0, best = -1, first = 0, last = 0; for (int i = 1; i < n; i++) { load += diff[i]; if (load > best) { best = load; first = last = i; } else if (load == best) { last = i; } } std::cout << best << " " << first << " " << last << "\n";}
Cmain.c · 25 lines
#include <stdio.h>static int diff[10000];int main(void) { int n, m, a, b; scanf("%d %d", &n, &m); for (int k = 0; k < m; k++) { scanf("%d %d", &a, &b); diff[a]++; /* a번 구간부터 한 명 늘고 */ diff[b]--; /* b번 정류장에서 내리니 b번 구간부터 준다 */ } int load = 0, best = -1, first = 0, last = 0; for (int i = 1; i < n; i++) { load += diff[i]; if (load > best) { best = load; first = last = i; } else if (load == best) { last = i; } } printf("%d %d %d\n", best, first, last); return 0;}
Craykonmain.cray · 30 lines
first = Console.ReadNumbers();n = first[0];m = first[1];// 차이 목록: a번 구간부터 한 명 늘고, b번 구간부터 한 명 준다diff = NewList(n + 1, 0);for (k = 0; k < m; k++){ p = Console.ReadNumbers(); diff[p[0]] += 1; diff[p[1]] -= 1;}load = 0;best = -1;from = 0;to = 0;for (i = 1; i < n; i++){ load += diff[i]; if (load > best) { best = load; from = i; to = i; } else if (load == best) { to = i; }}Console.WriteLine(best + " " + from + " " + to);