亚麻 OA 心疼崩了的OA1

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

第二题用 sweepline 解。
代码如下, time complexity O(nlogn)

1. class Solution {
   
2.   public int maxValue(int n, int[][] rounds) {
   
3.     class Point {
   
4.       final int index; // from 1 to n + 1
   
5.       final int type; // 1: left, -1: right
   
6.       final int contribution;
   
7.       Point(int index, int type, int contribution) {
   
8.         this.index = index;
   
9.         this.type = type;
   
10.         this.contribution = contribution;
    
11.       }
    
12.     }
    
13.    
    
14.     List<Point> sweepline = new ArrayList<>();
    
15.     for (int i = 0; i < rounds.length; i++) {
    
16.       sweepline.add(new Point(rounds[i][0], 1, rounds[i][2]));
    
17.       sweepline.add(new Point(rounds[i][1] + 1, -1, rounds[i][2]));
    
18.     }
    
19.    
    
20.     Collections.sort(sweepline, (Point s, Point t) -> {
    
21.       if (s.index == t.index) {
    
22.         return s.type - t.type; //if have same index, put right points ahead
    
23.       }
    
24.       return s.index - t.index;
    
25.     });
    
26.    
    
27.     int ans = 0;
    
28.     int curValue = 0;
    
29.     for (Point point : sweepline) {
    
30.       curValue += (point.contribution * point.type);
    
31.       ans = Math.max(ans, curValue);
    
32.     }
    
33.     return ans;
    
34.   }
    
35. }

复制代码

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

第二题leetcode上有原题370 ， 楼主收到OA2了吗