Tuesday, September 22, 2020

LeetCode [715] Range Module

 715. Range Module

Hard

A Range Module is a module that tracks ranges of numbers. Your task is to design and implement the following interfaces in an efficient manner.

  • addRange(int left, int right) Adds the half-open interval [left, right), tracking every real number in that interval. Adding an interval that partially overlaps with currently tracked numbers should add any numbers in the interval [left, right) that are not already tracked.

  • queryRange(int left, int right) Returns true if and only if every real number in the interval [left, right) is currently being tracked.

  • removeRange(int left, int right) Stops tracking every real number currently being tracked in the interval [left, right).

    • Example 1:

    addRange(10, 20): null
removeRange(14, 16): null
queryRange(10, 14): true (Every number in [10, 14) is being tracked)
queryRange(13, 15): false (Numbers like 14, 14.03, 14.17 in [13, 15) are not being tracked)
queryRange(16, 17): true (The number 16 in [16, 17) is still being tracked, despite the remove operation)

    Note:

  • A half open interval [left, right) denotes all real numbers left <= x < right.
  • 0 < left < right < 10^9 in all calls to addRange, queryRange, removeRange.
  • The total number of calls to addRange in a single test case is at most 1000.
  • The total number of calls to queryRange in a single test case is at most 5000.
  • The total number of calls to removeRange in a single test case is at most 1000.

    •  1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
    class RangeModule {
    TreeMap<Integer, Integer> map = new TreeMap<>();
    public RangeModule() {
        
    }
    
    //remove [l, r]
    int[] remove(int start, int end){
        int l = start, r = end;
        Map.Entry<Integer, Integer> lEntry = map.floorEntry(l);
        if(lEntry!=null && lEntry.getValue()>=l){
            l = lEntry.getKey();
        }
        Map.Entry<Integer, Integer> rEntry = map.floorEntry(r);
        if(rEntry!=null && rEntry.getValue()>=r){
            r = rEntry.getValue();
        }
        Map<Integer, Integer> submap = map.subMap(l, true, r, true);
        Set<Integer> set = new HashSet<>(submap.keySet());
        map.keySet().removeAll(set);
        return new int[]{l, r};
    }

    public void addRange(int left, int right) {
        int[] intv = remove(left, right);
        map.put(intv[0], intv[1]);
    }
    
    public boolean queryRange(int left, int right) {
        int l = left;
        Map.Entry<Integer, Integer> lEntry = map.floorEntry(l);
        if(lEntry==null) return false;
        if(lEntry.getValue()>=right) return true;
        return false;
    }
    
    public void removeRange(int left, int right) {
        int[] intv = remove(left, right);
        if(intv[0]<left) map.put(intv[0], left);
        if(right<intv[1]) map.put(right, intv[1]);
    }
}

/**
 * Your RangeModule object will be instantiated and called as such:
 * RangeModule obj = new RangeModule();
 * obj.addRange(left,right);
 * boolean param_2 = obj.queryRange(left,right);
 * obj.removeRange(left,right);
 */


    YMSF


     1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
    package MJ0208;

/*
给一个乱序数组如 [4 3 7 6 9 2] 定义一个range k, 如果任意两个数之间绝对值的差小于k,这两个数就属于同一数组，
如果a,b同属一组，a,c也同属一组，则b,c也同属一组，最终将小组分类好，返回分类好的组合，比如之前这个例子, 
如果k=1 则 result = [[4 3 2],[7 6],[9]]，此题不知道蠡口上有没有，如果有的话还请见多识广的大家提供的题号，
我感觉我准备的方法不是面试官期望的最优解，我是现将数组排序，然后检查相邻数字归入一组，如果超出range就新开一组，
但是这次要求保持同一小组内数字原有的相对顺序，所以我还开了一个tuple记录原来的顺序，然后小组内排序，总之感觉整的挺麻烦的。
我这算法的时间复杂度应该是O(nlogn) 空间是O(n)
*/

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Solution sol = new Solution();
        List<List<Integer>> list = sol.findGroupWithinRangeK(new int[]{4,3,7,6,9,2}, 1);
        System.out.println(Arrays.toString(list.toArray()));
    }
}

class Solution {
    class Intv{
        int left, right;
        List<Integer> members;
        Intv(int _l, int _r){
            left = _l;
            right = _r;
            members = new ArrayList<>();
        }
    }

    void removeRanges(TreeSet<Intv> groups, int left, int right){
        TreeSet<Intv> tmp = new TreeSet<>();
        for(Intv intv : groups){
            if(intv.right<left && intv.left>right){
                tmp.add(intv);
            }
        }
        groups = tmp;
    }

    List<List<Integer>> findGroupWithinRangeK(int[] arr, int K){
        TreeSet<Intv> groups = new TreeSet<>((a,b)->a.right-b.right);//interval's start point
        for(int a : arr){
            int left = a-K, right = a+K;

            Intv lIntv = groups.ceiling(new Intv(left, left));
            Intv rIntv = groups.ceiling(new Intv(right, right));

            if(lIntv!=null){
                int newLeft = Math.min(left, lIntv.left);
                int newRight = right;
                if(rIntv!=null){
                    newRight = Math.max(newRight, rIntv.right);
                }
                removeRanges(groups, newLeft, newRight);
                groups.add(new Intv(newLeft, newRight));
            }else{
                groups.add(new Intv(left, right));
            }
        }

        for(int a : arr){
            Intv intv = groups.ceiling(new Intv(a, a));
            intv.members.add(a);
        }

        List<List<Integer>> list = new ArrayList<>();
        for(Intv intv : groups){
            list.add(intv.members);
        }

        return list;
    }
}
    Posted by at

    No comments:

    Post a Comment

    Subscribe to: Post Comments (Atom)