LeetCode关于Interval的问题- LeetCode Range Module解法

Dear 丶 2023-06-23 05:53 2阅读 0赞

# LeetCode关于Interval的问题 #

关于我的 Leetcode 题目解答，代码前往 Github：[https://github.com/chenxiangcyr/leetcode-answers][https_github.com_chenxiangcyr_leetcode-answers]

--------------------

**LeetCode题目：**[56. Merge Intervals][]  
Given a collection of intervals, merge all overlapping intervals.

For example,  
Given `[1,3],[2,6],[8,10],[15,18]`,  
return `[1,6],[8,10],[15,18]`.

/**
 * Definition for an interval.
 * public class Interval {
 * int start;
 * int end;
 * Interval() { start = 0; end = 0; }
 * Interval(int s, int e) { start = s; end = e; }
 * }
 */
 class Solution {
 public List<Interval> merge(List<Interval> intervals) {
 
 // sort based on start time
 Collections.sort(intervals, new Comparator<Interval>() {
 public int compare(Interval i1, Interval i2) {
 return i1.start - i2.start;
 }
 });
 
 LinkedList<Interval> result = new LinkedList<Interval>();
 
 
 for(Interval interval : intervals) {
 if(result.isEmpty() || result.getLast().end < interval.start) {
 result.add(interval);
 }
 else {
 result.getLast().end = Math.max(result.getLast().end, interval.end);
 }
 }
 
 return result;
 }
 }

**LeetCode题目：**[57. Insert Interval][]  
Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary).

You may assume that the intervals were initially sorted according to their start times.

Example 1:  
Given intervals `[1,3],[6,9]`, insert and merge `[2,5]` in as `[1,5],[6,9]`.

Example 2:  
Given `[1,2],[3,5],[6,7],[8,10],[12,16]`, insert and merge `[4,9]` in as `[1,2],[3,10],[12,16]`.

This is because the new interval `[4,9]` overlaps with `[3,5],[6,7],[8,10]`.

/**
 * Definition for an interval.
 * public class Interval {
 * int start;
 * int end;
 * Interval() { start = 0; end = 0; }
 * Interval(int s, int e) { start = s; end = e; }
 * }
 */
 class Solution {
 public List<Interval> insert(List<Interval> intervals, Interval newInterval) {
 
 // the intervals were initially sorted according to their start times
 Iterator<Interval> itr = intervals.iterator();
 
 int originalSize = intervals.size();
 
 int idx = 0;
 while(itr.hasNext()) {
 Interval curInterval = itr.next();
 
 if(newInterval.end < curInterval.start) {
 break;
 }
 
 // merge if overlap
 if(isOverlapped(curInterval, newInterval)) {
 newInterval = mergeOverlapped(curInterval, newInterval);
 itr.remove();
 }
 
 idx++;
 }
 
 
 int newSize = intervals.size();
 
 int diff = originalSize - newSize;
 
 intervals.add(idx - diff, newInterval);
 
 
 return intervals;
 }
 
 public boolean isOverlapped(Interval i1, Interval i2) {
 
 if(i1.start <= i2.end && i2.start <= i1.end) {
 return true;
 }
 
 return false;
 }
 
 public Interval mergeOverlapped(Interval i1, Interval i2) {
 return new Interval(
 Math.min(i1.start, i2.start), 
 Math.max(i1.end, i2.end)
 );
 }
 }

**LeetCode题目：**[715. Range Module][]  
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`.

具体思路参见 [https://leetcode.com/articles/range-module/][https_leetcode.com_articles_range-module]  
关于 TreeSet，参见 [红黑树的Java实现TreeSet及相关LeetCode题目][Java_TreeSet_LeetCode]

class RangeModule {
 class Interval implements Comparable<Interval> {
 int left;
 int right;
 
 public Interval(int left, int right){
 this.left = left;
 this.right = right;
 }
 
 public int compareTo(Interval that){
 if (this.right == that.right) return this.left - that.left;
 
 return this.right - that.right;
 }
 }
 
 TreeSet<Interval> ranges;
 
 public RangeModule() {
 ranges = new TreeSet<Interval>();
 }
 
 public void addRange(int left, int right) {
 // tailSet: Returns a view of the portion of this set whose elements are greater than or equal to fromElement.
 Iterator<Interval> itr = ranges.tailSet(new Interval(0, left - 1)).iterator();
 
 while (itr.hasNext()) {
 Interval iv = itr.next();
 if (right < iv.left) break;
 left = Math.min(left, iv.left);
 right = Math.max(right, iv.right);
 itr.remove();
 }
 
 ranges.add(new Interval(left, right));
 }
 
 public void removeRange(int left, int right) {
 // tailSet: Returns a view of the portion of this set whose elements are greater than or equal to fromElement.
 Iterator<Interval> itr = ranges.tailSet(new Interval(0, left)).iterator();
 
 ArrayList<Interval> todo = new ArrayList();
 
 while (itr.hasNext()) {
 Interval iv = itr.next();
 if (right < iv.left) break;
 
 if (iv.left < left) todo.add(new Interval(iv.left, left));
 if (right < iv.right) todo.add(new Interval(right, iv.right));
 
 itr.remove();
 }
 
 for (Interval iv: todo) ranges.add(iv);
 }
 
 public boolean queryRange(int left, int right) {
 Interval in = ranges.higher(new Interval(0, left));
 
 if(in != null && in.left <= left && in.right >= right) {
 return true;
 }
 
 return false;
 }
 }
 
 /**
 * 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);
 */

**LeetCode题目：**[616. Add Bold Tag in String][] 
iven a string s and a list of strings dict, you need to add a closed pair of bold tag and to wrap the substrings in s that exist in dict. If two such substrings overlap, you need to wrap them together by only one pair of closed bold tag. Also, if two substrings wrapped by bold tags are consecutive, you need to combine them.

> Example 1: 
> Input: 
> s = "abcxyz123" 
> dict = \["abc","123"\] 
> Output: 
> "abcxyz123"

> Example 2: 
> Input: 
> s = "aaabbcc" 
> dict = \["aaa","aab","bc"\] 
> Output: 
> "aaabbcc"

Note:

*  The given dict won't contain duplicates, and its length won't exceed 100.
 *  All the strings in input have length in range \[1, 1000\].

class Solution {
 public String addBoldTag(String s, String[] dict) {
 List<Interval> tags = new ArrayList<>();
 
 if(s.isEmpty()) return s;
 
 for(String word : dict) {
 int wordLength = word.length();
 
 for(int i = 0; i <= s.length() - wordLength; i++) {
 String subString = s.substring(i, i + wordLength);
 
 if(subString.equals(word)) {
 tags.add(new Interval(i, i + wordLength - 1));
 }
 }
 }
 
 tags = merge(tags);
 
 StringBuilder sb = new StringBuilder(s);
 int count = 0;
 for(Interval i : tags) {
 System.out.println(i.left + ":" + i.right);
 
 sb.insert(count * 7 + i.left, "");
 sb.insert(count * 7 + 3 + i.right + 1, "");
 
 count++;
 }
 
 return sb.toString();
 }
 
 class Interval {
 int left;
 int right;
 
 Interval() { left = 0; left = 0; }
 Interval(int s, int e) { left = s; right = e; }
 }
 
 public List<Interval> merge(List<Interval> intervals) {
 
 // sort based on start time
 Collections.sort(intervals, new Comparator<Interval>() {
 public int compare(Interval i1, Interval i2) {
 return i1.left - i2.left;
 }
 });
 
 LinkedList<Interval> result = new LinkedList<Interval>();
 
 
 for(Interval interval : intervals) {
 if(result.isEmpty() || result.getLast().right < (interval.left - 1)) {
 result.add(interval);
 }
 else {
 result.getLast().right = Math.max(result.getLast().right, interval.right);
 }
 }
 
 return result;
 }
 }

[https_github.com_chenxiangcyr_leetcode-answers]: https://github.com/chenxiangcyr/leetcode-answers
[56. Merge Intervals]: https://leetcode.com/problems/merge-intervals/description/
[57. Insert Interval]: https://leetcode.com/problems/insert-interval/description/
[715. Range Module]: https://leetcode.com/problems/range-module/description/
[https_leetcode.com_articles_range-module]: https://leetcode.com/articles/range-module/
[Java_TreeSet_LeetCode]: https://www.jianshu.com/p/e994c44dad09
[616. Add Bold Tag in String]: https://leetcode.com/problems/add-bold-tag-in-string/description/