java - Java 中的范围简化

Question

我有一个 Range 对象，它由最小值和最大值组成。因此，可以有这样的范围

[1, 5]
[6, 12]
[13, 14]

这是我的问题。假设您有一个由以下给出的范围列表

ArrayList<Range> ranges;

并且您想要修复它们，以便不存在重叠范围。即有两个函数:

public void addRange(Range r);

public void removeRange(Range r);

您可能会假设在每个方法之后，ranges ArrayList 将始终按最小值排序。请注意，ranges ArrayList 始终包含初始范围[1, 100]。以下是一些前后范围的示例:

ranges = {[1,5], [6,12], [13,14]}
addRange([7, 15])
ranges = {[1,5], [6,15]}

ranges = {[1,12], [18,29], [34,89]}
addRange([16,17])
ranges = {{[1,12], [16,17], [18,29], [34,89]}

ranges = {[16,35]}
removeRange([19,54])
ranges = {[16,19]}

如何编写这两个函数？

Answer 1

这应该有效。它的时间复杂度为 O(n)，因此您可能需要替换更快的搜索/排序算法。

DistinctRangeList.java

package range;

import java.util.LinkedList;

public class DistinctRangeList {

    private LinkedList<Range> linkedList;

    public DistinctRangeList() {
        linkedList = new LinkedList<Range>();
    }

    public void add(Range newRange) {
        for (int i = 0; i < linkedList.size(); i++) {
            Range range = linkedList.get(i);
            if (range.overlaps(newRange)) {
                return;
            } else if (newRange.min < range.min) {
                linkedList.add(i, newRange);
                return;
            } else {
                continue;
            }
        }
        linkedList.addLast(newRange);
    }

    public void remove(Range remove) {
        for (int i = 0; i < linkedList.size(); i++) {
            Range range = linkedList.get(i);
            if (range.equals(remove)) {
                linkedList.remove(range);   
            }
        }
    }

    public String toString() {
        String s = "";
        for (Range r : linkedList) {
            s += String.format("[%d, %d] ", r.min, r.max);
        }
        return s;
    }

    public static void main(String[] args) {
        DistinctRangeList lst = new DistinctRangeList();
        lst.add(new Range(3, 6)); // should add
        lst.add(new Range(3, 5)); // should not add
        lst.add(new Range(7, 8)); // should add
        lst.add(new Range(10, 15)); // should add
        lst.remove(new Range(10, 15)); 
        lst.add(new Range(10, 12)); // should add
        lst.add(new Range(1, 2)); // should add to the beginning
        System.out.println(lst);
    }
}

Range.java

package range;

public class Range {
    public int min, max;

    public Range(int min, int max) {
        this.min = min; this.max = max;
    }

    public boolean equals(Range other) {
        return this.min == other.min && this.max == other.max;
    }

    public boolean overlaps(Range other) {
        return (min <= other.min && other.min <= max) ||
               (min <= other.max && other.max <= max);
    }
}

---

好吧，我想这就是你想要的。 (这是一个有趣的问题，所以我继续解决它。)

RangeSet.java

package range;

import java.util.LinkedList;

public class RangeSet {

    private LinkedList<Range> linkedList;

    public RangeSet() {
        linkedList = new LinkedList<Range>();
    }

    public void add(Range range) {

        System.out.println("Adding " + range + " ...");

        if (linkedList.contains(range)) {
            return;
        }

        // First place the new range
        boolean done = false;
        for (int i = 0; i < linkedList.size() && !done; i++) {
            Range current = linkedList.get(i);
            if (range.min < current.min) {
                linkedList.add(i, range);
                done = true;
            }
        }
        if (!done) {
            linkedList.addLast(range);
        }

        // Now, do the necessary merges
        for (int i = 0; i < linkedList.size() - 1; i++) {
            Range current = linkedList.get(i);
            Range next = linkedList.get(i + 1);
            if (current.overlaps(next)) {
                current.extendBy(next);
                linkedList.remove(i + 1);
            }
        }

        System.out.println(this);
    }

    public void remove(Range remove) {

        System.out.println("Removing " + remove + " ...");

        for (int i = 0; i < linkedList.size(); i++) {

            Range current = linkedList.get(i);

            if (!current.overlaps(remove)) { // no overlap

                continue;

            } else if (remove.min <= current.min && remove.max >= current.max) { // the range to remove contains the current node

                linkedList.remove(i);

            } else if (remove.min < current.min) { // the range to remove intersects the current node from the left end

                current.min = remove.max;

            } else if (remove.max > current.max) { // [...] from the right end

                current.max = remove.min;

            } else { // the range to remove is contained within the current node, splitting it in two

                Range start = new Range(current.min, remove.min);

                Range end = new Range(remove.max, current.max);

                linkedList.remove(i);

                linkedList.add(i, start);

                linkedList.add(i + 1, end);
            }
        }

        System.out.println(this);
    }

    public String toString() {
        String s = "";
        for (Range r : linkedList) {
            s += r.toString() + " ";
        }
        return s;
    }

    public static void main(String[] args) {
        RangeSet set = new RangeSet();
        set.add(new Range(3, 6));
        set.add(new Range(1, 2));
        set.add(new Range(4, 10));
        set.add(new Range(50, 100));
        set.remove(new Range(9, 90));
        System.out.println("Final result:\n" + set);
    }
}

Range.java

package range;

public class Range {
    public int min, max;

    public Range(int min, int max) {
        this.min = min; this.max = max;
    }

    public boolean equals(Range other) {
        return this.min == other.min && this.max == other.max;
    }

    public boolean overlaps(Range other) {
        return (min <= other.min && other.min <= max) ||
               (min <= other.max && other.max <= max);
    }

    public void extendBy(Range other) {
        if (other.min < this.min) {
            this.min = other.min;
        }
        if (other.max > this.max) {
            this.max = other.max;
        }
    }

    public String toString() {
        return String.format("[%d, %d]", min, max);
    }
}