<
查看: 1494| 回复: 13
收起左侧

[数组] 大家好,希望求助大家一道算法题。

woshimajia1 | 显示全部楼层
本楼:   👍  0
0%
0%
0   👎
全局:   37
90%
10%
4

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

x

give a list of ranges and a range  (can have any start point) with fixed length L , what is the maximum number of ranges L can cover.
举个例子
[1, 2], [3, 5], [2, 10], [3, 7], 给定一个长度为5的range。
那么结果就为2, 因为[1, 2], [3, 5]可以一个长度为5的range cover, 想问一下有什么有效的算法解决这个问题


换一个例子
[1, 2], [3, 5], [2, 10], [3, 7], 给定一个长度为7的range
那么结果就为3, 因为[1, 2], [3, 5] [3, 7]可以一个长度为5的range cover, 想问一下有什么有效的算法解决这个问题

评分

参与人数 1大米 +2 收起 理由
14417335 + 2 给你点个赞!

查看全部评分


上一篇:[LC周赛赛后发布会] Weekly Contest 380
下一篇:之前见过的一道题 想不太清楚 求建议
yseLong 2024-1-19 23:51:25 来自APP | 显示全部楼层
本楼:   👍  2
100%
0%
0   👎
全局:   110
85%
15%
20
额,确实很简单,但是前面用two pointers的答案都是错的,应该用 sweep line。。。

补充内容 (2024-01-20 00:06 +08:00):
算了,也不算 sweep line。就是按右端点sort 一下, 再 scan 一下,同时维护一个合法左端点的最小堆,最大的合法左端点的最小堆的大小就是返回值
回复

使用道具 举报

Diandian459 2024-1-19 15:56:24 | 显示全部楼层
本楼:   👍  2
100%
0%
0   👎
全局:   36
97%
3%
1
按右端点不降排序+小顶堆维护合法的左端点+滑动窗口遍历。时间N*logN,线性空间
  1. import java.util.*;

  2. class Solution {
  3.        
  4.         public int maxCover(int[][] ranges, int span) {
  5.                 // 右端点不降排序
  6.                 Arrays.sort(ranges, (a,b)->a[1]-b[1]);
  7.                 // 合法左端点优先队列
  8.                 PriorityQueue<Integer> lefts = new PriorityQueue<>();
  9.                 int res = 0;
  10.                 // 滑动窗口
  11.                 for(int[] range : ranges) {
  12.                         int r = range[1];
  13.                         int l = r-span;
  14.                         lefts.add(range[0]);
  15.                         // 剔除不合法
  16.                         while(!lefts.isEmpty() && lefts.peek()<l) {
  17.                                 lefts.poll();
  18.                         }
  19.                         // 更新答案
  20.                         res = Math.max(res, lefts.size());
  21.                 }
  22.                 return res;
  23.         }
  24.        
  25.     public static void main(String[] args) {
  26.            
  27.             Solution s = new Solution();
  28.             int res = s.maxCover(new int[][] {{1,2},{3,5},{2,10},{3,7}}, 7);
  29.             System.out.print(res);
  30.     }
  31. }
复制代码

评分

参与人数 1大米 +2 收起 理由
14417335 + 2 给你点个赞!

查看全部评分

回复

使用道具 举报

tyang313 2024-1-19 05:18:07 来自APP | 显示全部楼层
本楼:   👍  1
100%
0%
0   👎
全局:   2002
88%
12%
271
Two pointer, 算是easy -medium题
回复

使用道具 举报

SoyTuPapa 2024-1-19 06:06:05 来自APP | 显示全部楼层
本楼:   👍  0
0%
0%
0   👎
全局:   1195
97%
3%
42
几段ranges的话长度是怎么计算? 是最后的range的右端点减去最左的range的左端点吗? 比如 [2,3][4,8]的话长度是8-2?
回复

使用道具 举报

 楼主| woshimajia1 2024-1-19 07:55:40 | 显示全部楼层
本楼:   👍  0
0%
0%
0   👎
全局:   37
90%
10%
4
SoyTuPapa 发表于 2024-1-18 14:06
几段ranges的话长度是怎么计算? 是最后的range的右端点减去最左的range的左端点吗? 比如 [2,3][4,8]的话 ...

对的 对于长度为5的range 和一个 list [1, 2], [1, 3], [1, 5], [2, 5]
那么长度为5的range可以cover 上面4个
回复

使用道具 举报

 楼主| woshimajia1 2024-1-19 07:56:10 | 显示全部楼层
本楼:   👍  0
0%
100%
1   👎
全局:   37
90%
10%
4
tyang313 发表于 2024-1-18 13:18
Two pointer, 算是easy -medium题

easy to medium?能否给个code 多谢
回复

使用道具 举报

SoyTuPapa 2024-1-19 08:12:10 来自APP | 显示全部楼层
本楼:   👍  0
0%
0%
0   👎
全局:   1195
97%
3%
42
woshimajia1 发表于 2024-01-18 15:55:40
对的 对于长度为5的range 和一个 list , , ,
那么长度为5的range可以cover 上面4个
有数据范围吗? 比如最多能有多少个ranges和fixed length L多大?
回复

使用道具 举报

 楼主| woshimajia1 2024-1-19 08:17:54 | 显示全部楼层
本楼:   👍  0
0%
100%
1   👎
全局:   37
90%
10%
4
SoyTuPapa 发表于 2024-1-18 16:12
有数据范围吗? 比如最多能有多少个ranges和fixed length L多大?

比如range个数小于10^5, range maximum value <= 10^5, length <= 10^5
回复

使用道具 举报

阵雨 2024-1-19 08:24:38 | 显示全部楼层
本楼:   👍  0
0%
100%
1   👎
全局:   2455
94%
6%
143
def max_covered_ranges(ranges, L):
    # Step 1: Sort ranges by start point
    ranges.sort(key=lambda x: x[1])

    max_cover = 0
    for i in range(len(ranges)):
        cover = 0
        # Determine the end point of the sliding window
        window_end = ranges[i][0] + L

        # Step 3: Count how many ranges are covered by this window
        for j in range(i, len(ranges)):
            if ranges[j][1] <=  window_end:
                cover += 1
            else:
                if ranges[j][0] > window_end:
                    break

        # Step 4: Update maximum coverage if necessary
        max_cover = max(max_cover, cover)

    return max_cover

# Test the function with the given example
example_ranges = [(1, 2), (3, 5), (2, 10), (3, 7)]

print(max_covered_ranges(example_ranges, 5))
print(max_covered_ranges(example_ranges, 7))
print(max_covered_ranges(example_ranges, 10))

gpt 稍微改下貌似就可以了
回复

使用道具 举报

tyang313 2024-1-19 08:59:33 | 显示全部楼层
本楼:   👍  0
0%
100%
3   👎
全局:   2002
88%
12%
271
woshimajia1 发表于 2024-1-18 15:56
easy to medium?能否给个code 多谢

def solution(ranges, x):

    ranges.sort(key = lambda x: x[1])
    i = j = 0
    res = 0

    while j < len(ranges):

        if ranges[j][1] - ranges[j][0] >= x:
            j += 1
            i = j
        else:
            while i < j and ranges[j][1] - ranges[i][0] >= x:
                i += 1
        res = max(res, j-i+1)
        j += 1

    return res
回复

使用道具 举报

 楼主| woshimajia1 2024-1-19 11:10:49 | 显示全部楼层
本楼:   👍  0
0%
100%
2   👎
全局:   37
90%
10%
4
tyang313 发表于 2024-1-18 16:59
def solution(ranges, x):

    ranges.sort(key = lambda x: x[1])

很明显错了啊,你按照第二位排序,明显错误
[7,8], [1,10], ,[11,12] range为5
这个结果应该是2,按照end排序,结果为1
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

Advertisement
>
快速回复 返回顶部 返回列表