最小时间差

题目

给定一个 24 小时制(小时:分钟 "HH:MM")的时间列表, 找出列表中任意两个时间的最小时间差并以分钟数表示.

示例

输入: timePoints = ['23:59', '00:00']
输出: 1

输入: timePoints = ['00:00', '23:59', '00:00']
输出: 0

题解

1. 首先将时间换成分钟数字, 并对该数组从小到大排列
2. 最小时间差必然出现在 timePoints 的两个相邻时间, 或者 timePoints 的两个首尾时间中.

JavaScript

/**
 * @param {string[]} timePoints
 * @return {number}
 */
var findMinDifference = function (timePoints) {
  const n = timePoints.length

  // 根据题意, 一共有 24*60=1440 种不同的时间.
  // 由鸽巢原理可知, 如果 timePoints 的长度超过 1440, 那么必然会有两个相同的时间, 此时可以直接返回 0
  if (n > 24 * 60) {
    return 0
  }

  const minutes = timePoints.map((t) => parseTime(t)).sort((a, b) => a - b)
  let min = minutes[0] + 24 * 60 - minutes[n - 1]

  for (let i = 1; i < n; i++) {
    const prev = minutes[i - 1]
    const curr = minutes[i]
    min = Math.min(min, curr - prev)
  }

  return min
}

var parseTime = function (timePoints) {
  const [hour, minute] = timePoints.split(':')
  return +hour * 60 + +minute
}

Rust

use std::cmp;

fn parse_time(time: &String) -> i32 {
    let vec: Vec<&str> = time.split(":").collect();
    let hour = vec[0].parse::<i32>().unwrap();
    let minute = vec[1].parse::<i32>().unwrap();

    hour * 60 + minute
}

pub fn find_min_difference(time_points: Vec<String>) -> i32 {
    let n = time_points.len();

    if n > 24 * 60 {
        return 0;
    }

    let mut times = time_points
        .iter()
        .enumerate()
        .fold(vec![0; n], |mut times, (i, time)| {
            times[i] = parse_time(time);
            times
        });
    times.sort();

    let mut min = times[0] + 24 * 60 - times[times.len() - 1];

    for i in 1..n {
        let prev = times[i - 1];
        let curr = times[i];
        min = cmp::min(min, curr - prev)
    }

    min
}