(B卷,200分)- 观看文艺汇演问题（Java & JS & Python & C）

题目描述

为了庆祝中国共产党成立100周年，某公园将举行多场文艺表演，很多演出都是同时进行，一个人只能同时观看一场演出，且不能迟到早退，由于演出分布在不同的演出场地，所以连续观看的演出最少有15分钟的时间间隔，

小明是一个狂热的文艺迷，想观看尽可能多的演出， 现给出演出时间表，请帮小明计算他最多能观看几场演出。

输入描述

第一行为一个数N，表示演出场数，1<=N<=1000，接下来N行，每行有被空格分割的两个整数，

第一个整数T表示演出的开始时间，第二个整数L表示演出的持续时间，T和L的单位为分钟，0<=T<=1440,0<L<=100.

输出描述

输出最多能观看的演出场数。

用例

题目解析

本题其实是区间问题。且是要求解最多不相交区间个数。

需要注意的是，两个区间不相交的条件也比较特殊：

连续观看的演出最少有15分钟的时间间隔

即两个区间之间需要间隔15单位长度才算不相交。

关于最多不相交区间个数的求解，请看：

JavaScript算法源码

/* JavaScript Node ACM模式 控制台输入获取 */
const readline = require("readline");

const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

const lines = [];
let n;
rl.on("line", (line) => {
  lines.push(line);

  if (lines.length === 1) {
    n = lines[0] - 0;
  }

  if (n && lines.length === n + 1) {
    lines.shift();
    const matrix = lines.map((line) => line.split(" ").map(Number));
    console.log(getResult(matrix));
    lines.length = 0;
  }
});

function getResult(matrix) {
  matrix = matrix
    .map(([start, spend]) => [start, start + spend])
    .sort((a, b) => a[1] - b[1]);

  let t = matrix[0][1];
  let ans = 1;
  for (let i = 1; i < matrix.length; i++) {
    const [l, r] = matrix[i];

    if (l - t >= 15) {
      ans++;
      t = r;
    }
  }

  return ans;
}

Java算法源码

import java.util.Arrays;
import java.util.Scanner;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);

    int n = sc.nextInt();

    int[][] ranges = new int[n][2];
    for (int i = 0; i < n; i++) {
      ranges[i][0] = sc.nextInt(); // 开始时间
      ranges[i][1] = ranges[i][0] + sc.nextInt(); // 结束时间 = 开始时间 + 持续时间
    }

    System.out.println(getResult(ranges));
  }

  public static int getResult(int[][] ranges) {
    Arrays.sort(ranges, (a, b) -> a[1] - b[1]);

    int t = ranges[0][1];
    int ans = 1;

    for (int i = 1; i < ranges.length; i++) {
      int l = ranges[i][0];
      int r = ranges[i][1];

      if (l - t >= 15) {
        ans++;
        t = r;
      }
    }

    return ans;
  }
}

Python算法源码

# 输入获取
n = int(input())
tmp = [list(map(int, input().split())) for _ in range(n)]
rans = list(map(lambda ran: [ran[0], ran[0] + ran[1]], tmp))


# 算法入口
def getResult():
    rans.sort(key=lambda ran: ran[1])

    t = rans[0][1]
    ans = 1

    for i in range(1, len(rans)):
        l, r = rans[i]
        if l - t >= 15:
            ans += 1
            t = r

    return ans


# 算法调用
print(getResult())

C算法源码

#include <stdio.h>
#include <stdlib.h>

int cmp(const void* a, const void* b) {
    return ((int*) a)[1] - ((int*) b)[1];
}

int main() {
    int n;
    scanf("%d", &n);

    int ranges[n][2];
    for(int i=0; i<n; i++) {
        scanf("%d %d", &ranges[i][0], &ranges[i][1]);
        ranges[i][1] += ranges[i][0];
    }

    qsort(ranges, n, sizeof(int*), cmp);

    int t = ranges[0][1];
    int ans = 1;

    for(int i=1; i<n; i++) {
        int l = ranges[i][0];
        int r = ranges[i][1];

        if(l - t >= 15) {
            ans++;
            t = r;
        }
    }

    printf("%dn", ans);

    return 0;
}