Minimum Interval to Include Each Query

January 10, 2025

Finding the Minimum Interval to Include Each Query

Handling ranges and efficiently answering queries based on given intervals is a common challenge in programming.

This article explores how to determine the shortest interval that includes a specific query point. If no such interval exists, the result should indicate that explicitly.

Problem Description

You are given:

A 2D array intervals, where each interval is represented as [left, right].
- These intervals are inclusive, meaning a point $p$ is considered within an interval if $\leq p \leq right$ .
An array of queries, where each query asks for the shortest interval that includes the query point.

Your Task:

For each query $q$ , return:

The length of the shortest interval that includes $q$ .
If no interval contains $q$ , return -1.

Key Notes:

The length of an interval $[l e f t, r i g h t]$ is calculated as $length=right−left+1\text{length} = \text{right} – \text{left} + 1$ .

Example 1

Input: intervals = [[1,3],[2,3],[3,7],[6,6]], queries = [2,3,1,7,6,8]

Output: [2,2,3,5,1,-1]

Explanation:

Query = 2: The interval [2,3] is the smallest one containing 2, it’s length is 2.
Query = 3: The interval [2,3] is the smallest one containing 3, it’s length is 2.
Query = 1: The interval [1,3] is the smallest one containing 1, it’s length is 3.
Query = 7: The interval [3,7] is the smallest one containing 7, it’s length is 5.
Query = 6: The interval [6,6] is the smallest one containing 6, it’s length is 1.
Query = 8: There is no interval containing 8.

Example 2

Input: intervals = [(4,9)]

Output: 1

Constraints:

1 <= intervals.length <= 1000
1 <= queries.length <= 1000
1 <= left_i <= right_i <= 10000
1 <= queries[j] <= 10000

Key Idea:

Sort Intervals and Queries:
Sorting intervals by length ensures that we evaluate shorter intervals first. Sorting queries allows us to process them efficiently in ascending order.
Use a Min-Heap to Track Active Intervals:
As we process each query, maintain a min-heap of intervals that could potentially include the query point. Remove intervals from the heap when they can no longer contain the current query.
Binary Search or Sliding Window for Interval Selection:
Efficiently match intervals to queries by leveraging their sorted order.

Algorithm

Preprocessing:
- Sort intervals by length ( $right−left+1\text{right} – \text{left} + 1$ ).
- Sort queries while keeping track of their original indices.
Initialize a Min-Heap:
- Use the heap to store intervals currently valid for the query. The heap stores intervals as $(length,right,left)(\text{length}, \text{right}, \text{left})$ .
Process Queries:
- For each query in sorted order:
  - Add intervals to the heap if the interval’s left is less than or equal to the query.
  - Remove intervals from the heap if the interval’s right is less than the query.
  - If the heap is not empty, the top of the heap gives the shortest valid interval for the query. Otherwise, return -1.
Output the Results:
- Return the results in the original query order.

There are mainly Four approach to solve this problem –

Brute Force
Sweep Line Algorithm
Min Heap
Min Segment Tree (Lazy Propagation)

1. Brute Force

Time complexity: O(m∗n)
Space complexity:

Python

C++

Java

JavaScript

Python

class Solution:
    def minInterval(self, intervals: List[List[int]], queries: List[int]) -> List[int]:
        n = len(intervals)
        res = []
        for q in queries:
            cur = -1
            for l, r in intervals:
                if l <= q <= r:
                    if cur == -1 or (r - l + 1) < cur:
                        cur = r - l + 1
            res.append(cur)
        return res

C++

class Solution {
public:
    vector minInterval(vector>& intervals, vector& queries) {
        vector res;
        for (int q : queries) {
            int cur = -1;
            for (auto& interval : intervals) {
                int l = interval[0], r = interval[1];
                if (l <= q && q <= r) {
                    if (cur == -1 || (r - l + 1) < cur) {
                        cur = r - l + 1;
                    }
                }
            }
            res.push_back(cur);
        }
        return res;
    }
};

Java

public class Solution {
    public int[] minInterval(int[][] intervals, int[] queries) {
        int[] res = new int[queries.length];
        int idx = 0;
        for (int q : queries) {
            int cur = -1;
            for (int[] interval : intervals) {
                int l = interval[0], r = interval[1];
                if (l <= q && q <= r) {
                    if (cur == -1 || (r - l + 1) < cur) {
                        cur = r - l + 1;
                    }
                }
            }
            res[idx++] = cur;
        }
        return res;
    }
}

JavaScript

class Solution {
    /**
     * @param {number[][]} intervals
     * @param {number[]} queries
     * @return {number[]}
     */
    minInterval(intervals, queries) {
        const res = [];
        for (const q of queries) {
            let cur = -1;
            for (const [l, r] of intervals) {
                if (l <= q && q <= r) {
                    if (cur === -1 || (r - l + 1) < cur) {
                        cur = r - l + 1;
                    }
                }
            }
            res.push(cur);
        }
        return res;
    }
}

2. Sweep Line Algorithm

Time & Space Complexity

Time complexity:
Space complexity:

Where is the length of the array and is the length of the array

C++

Java

Python

JavaScript

C++

class Solution {
public:
    vector minInterval(vector>& intervals, vector& queries) {
        vector> events;
        // Create events for intervals
        for (int i = 0; i < intervals.size(); i++) {
            events.push_back({intervals[i][0], 0, intervals[i][1] - intervals[i][0] + 1, i});
            events.push_back({intervals[i][1], 2, intervals[i][1] - intervals[i][0] + 1, i});
        }
        
        // Create events for queries
        for (int i = 0; i < queries.size(); i++) {
            events.push_back({queries[i], 1, i});
        }
        
        // Sort by time and type (end before query)
        sort(events.begin(), events.end(), [](const vector& a, const vector& b) {
            return a[0] == b[0] ? a[1] < b[1] : a[0] < b[0];
        });
        
        vector ans(queries.size(), -1);
        // Min heap storing [size, index]
        priority_queue, vector>, greater>> pq;
        vector inactive(intervals.size(), false);
        
        for (const auto& event : events) {
            if (event[1] == 0) { // Interval start
                pq.push({event[2], event[3]});
            } else if (event[1] == 2) { // Interval end
                inactive[event[3]] = true;
            } else { // Query
                int queryIdx = event[2];
                while (!pq.empty() && inactive[pq.top().second]) {
                    pq.pop();
                }
                if (!pq.empty()) {
                    ans[queryIdx] = pq.top().first;
                }
            }
        }
        
        return ans;
    }
};

Java

public class Solution {
   public int[] minInterval(int[][] intervals, int[] queries) {
       List events = new ArrayList<>();
       for (int i = 0; i < intervals.length; i++) {
           events.add(new int[]{intervals[i][0], 0, intervals[i][1] - intervals[i][0] + 1, i});
           events.add(new int[]{intervals[i][1], 2, intervals[i][1] - intervals[i][0] + 1, i}); 
       }
       
       for (int i = 0; i < queries.length; i++) {
           events.add(new int[]{queries[i], 1, i});
       }
       
       // Sort by time and type (end before query)
       events.sort((a, b) -> a[0] != b[0] ? 
                  Integer.compare(a[0], b[0]) : 
                  Integer.compare(a[1], b[1]));
       
       int[] ans = new int[queries.length];
       Arrays.fill(ans, -1);
       
       // Min heap storing [size, index]
       PriorityQueue pq = new PriorityQueue<>((a, b) -> Integer.compare(a[0], b[0]));
       boolean[] inactive = new boolean[intervals.length];
       
       for (int[] event : events) {
           if (event[1] == 0) { // Interval start
               pq.offer(new int[]{event[2], event[3]});
           } 
           else if (event[1] == 2) { // Interval end
               inactive[event[3]] = true;
           } 
           else { // Query
               while (!pq.isEmpty() && inactive[pq.peek()[1]]) {
                   pq.poll();
               }
               if (!pq.isEmpty()) {
                   ans[event[2]] = pq.peek()[0];
               }
           }
       }
       
       return ans;
   }
}

Python

class Solution:
    def minInterval(self, intervals: List[List[int]], queries: List[int]) -> List[int]:
        events = []
        # Create events for intervals
        for idx, (start, end) in enumerate(intervals):
            events.append((start, 0, end - start + 1, idx))    
            events.append((end, 2, end - start + 1, idx))      
        
        # Create events for queries
        for i, q in enumerate(queries):
            events.append((q, 1, i))
        
        # Sort by time and type (end before query)
        events.sort(key=lambda x: (x[0], x[1]))
        
        # Min heap storing [size, index]
        sizes = []  
        ans = [-1] * len(queries)
        inactive = [False] * len(intervals)
        
        for time, type, *rest in events:
            if type == 0:  # Interval start
                interval_size, idx = rest
                heapq.heappush(sizes, (interval_size, idx))
            elif type == 2: #Interval end
                idx = rest[1]
                inactive[idx] = True
            else: # Query
                query_idx = rest[0]
                while sizes and inactive[sizes[0][1]]:
                    heapq.heappop(sizes)
                if sizes:
                    ans[query_idx] = sizes[0][0]
        
        return ans

JavaScript

class Solution {
    /**
     * @param {number[][]} intervals
     * @param {number[]} queries
     * @return {number[]}
     */
    minInterval(intervals, queries) {
        let events = [];
        // Create events for intervals
        for (let i = 0; i < intervals.length; i++) {
            const [start, end] = intervals[i];
            events.push([start, 0, end - start + 1, i]);
            events.push([end, 2, end - start + 1, i]);
        }

        // Create events for queries
        queries.forEach((q, i) => {
            events.push([q, 1, i]);
        });
        // Sort by time and type (end before query)
        events.sort((a, b) => a[0] - b[0] || a[1] - b[1]);

        const ans = Array(queries.length).fill(-1);
        // Min heap storing [size, index]
        const pq = new PriorityQueue((a, b) => a[0] - b[0]);
        const inactive = Array(intervals.length).fill(false);

        for (const [time, type, ...rest] of events) {
            if (type === 0) { // Interval start
                pq.push([rest[0], rest[1]]);
            } else if (type === 2) { // Interval end
                inactive[rest[1]] = true;
            } else { // Query
                while (!pq.isEmpty() && inactive[pq.front()[1]]) {
                    pq.pop();
                }
                if (!pq.isEmpty()) {
                    ans[rest[0]] = pq.front()[0];
                }
            }
        }
        
        return ans;
    }
}

3. Min Heap

Time complexity: O(nlogn+mlogm)
Space complexity: O(n+m)

C++

Java

Python

JavaScript

C++

/**
 * Definition of Interval:
 * class Interval {
 * public:
 *     int start, end;
 *     Interval(int start, int end) {
 *         this->start = start;
 *         this->end = end;
 *     }
 * }
 */

class Solution {
public:
    int minMeetingRooms(vector& intervals) {
        vector start, end;
        
        for (const auto& i : intervals) {
            start.push_back(i.start);
            end.push_back(i.end);
        }
        
        sort(start.begin(), start.end());
        sort(end.begin(), end.end());
        
        int res = 0, count = 0, s = 0, e = 0;
        while (s < intervals.size()) {
            if (start[s] < end[e]) {
                s++;
                count++;
            } else {
                e++;
                count--;
            }
            res = max(res, count);
        }
        return res;
    }
};

Java

public class Solution {
    public int[] minInterval(int[][] intervals, int[] queries) {
        Arrays.sort(intervals, Comparator.comparingInt(a -> a[0]));
        PriorityQueue minHeap = new PriorityQueue<>((a, b) -> Integer.compare(a[0], b[0]));
        Map res = new HashMap<>();
        int i = 0;
        for (int q : Arrays.stream(queries).sorted().toArray()) {
            while (i < intervals.length && intervals[i][0] <= q) {
                int l = intervals[i][0];
                int r = intervals[i][1];
                minHeap.offer(new int[]{r - l + 1, r});
                i++;
            }

            while (!minHeap.isEmpty() && minHeap.peek()[1] < q) {
                minHeap.poll();
            }
            res.put(q, minHeap.isEmpty() ? -1 : minHeap.peek()[0]);
        }
        int[] result = new int[queries.length];
        for (int j = 0; j < queries.length; j++) {
            result[j] = res.get(queries[j]);
        }
        return result;
    }
}

Python

class Solution:
    def minInterval(self, intervals: List[List[int]], queries: List[int]) -> List[int]:
        intervals.sort()
        minHeap = []
        res = {}
        i = 0
        for q in sorted(queries):
            while i < len(intervals) and intervals[i][0] <= q:
                l, r = intervals[i]
                heapq.heappush(minHeap, (r - l + 1, r))
                i += 1

            while minHeap and minHeap[0][1] < q:
                heapq.heappop(minHeap)
            res[q] = minHeap[0][0] if minHeap else -1
        return [res[q] for q in queries]

JavaScript

/**
 * const { MinPriorityQueue } = require('@datastructures-js/priority-queue');
 */

class Solution {
    /**
     * @param {number[][]} intervals
     * @param {number[]} queries
     * @return {number[]}
     */
    minInterval(intervals, queries) {
        intervals.sort((a, b) => a[0] - b[0]);
        const minHeap = new MinPriorityQueue(entry => entry[0]);
        const res = {};
        let i = 0;

        const sortedQueries = [...queries].sort((a, b) => a - b);

        for (const q of sortedQueries) {
            while (i < intervals.length && intervals[i][0] <= q) {
                const [l, r] = intervals[i];
                minHeap.enqueue([r - l + 1, r]);
                i += 1;
            }

            while (!minHeap.isEmpty() && minHeap.front()[1] < q) {
                minHeap.dequeue();
            }

            res[q] = !minHeap.isEmpty() ? minHeap.front()[0] : -1;
        }

        return queries.map(q => res[q]);
    }
}

4. Min Segment Tree (Lazy Propagation)

Time complexity: O(nlogn)
Space complexity:

C++

Java

Python

JavaScript

C++

class SegmentTree {
public:
    int n;
    vector tree;
    vector lazy;

    SegmentTree(int N) {
        this->n = N;
        tree.assign(4 * N, INT_MAX);
        lazy.assign(4 * N, INT_MAX);
    }

    void propagate(int treeidx, int lo, int hi) {
        if (lazy[treeidx] != INT_MAX) {
            tree[treeidx] = min(tree[treeidx], lazy[treeidx]);
            if (lo != hi) {
                lazy[2 * treeidx + 1] = min(lazy[2 * treeidx + 1], lazy[treeidx]);
                lazy[2 * treeidx + 2] = min(lazy[2 * treeidx + 2], lazy[treeidx]);
            }
            lazy[treeidx] = INT_MAX;
        }
    }

    void update(int treeidx, int lo, int hi, int left, int right, int val) {
        propagate(treeidx, lo, hi);
        
        if (lo > right || hi < left) return;

        if (lo >= left && hi <= right) {
            lazy[treeidx] = min(lazy[treeidx], val);
            propagate(treeidx, lo, hi);
            return;
        }

        int mid = (lo + hi) / 2;
        update(2 * treeidx + 1, lo, mid, left, right, val);
        update(2 * treeidx + 2, mid + 1, hi, left, right, val);
        
        tree[treeidx] = min(tree[2 * treeidx + 1], tree[2 * treeidx + 2]);
    }

    int query(int treeidx, int lo, int hi, int idx) {
        propagate(treeidx, lo, hi);
        if (lo == hi) return tree[treeidx];
        
        int mid = (lo + hi) / 2;
        if (idx <= mid) return query(2 * treeidx + 1, lo, mid, idx);
        else return query(2 * treeidx + 2, mid + 1, hi, idx);
    }

    void update(int left, int right, int val) {
        update(0, 0, n - 1, left, right, val);
    }

    int query(int idx) {
        return query(0, 0, n - 1, idx);
    }
};

class Solution {
public:
    vector minInterval(vector>& intervals, vector& queries) {
        vector points;

        for (const auto& interval : intervals) {
            points.push_back(interval[0]);
            points.push_back(interval[1]);
        }
        for (int q : queries) {
            points.push_back(q);
        }

        sort(points.begin(), points.end());
        points.erase(unique(points.begin(), points.end()), points.end());

        // compress the coordinates
        unordered_map compress;
        for (int i = 0; i < points.size(); ++i) {
            compress[points[i]] = i;
        }

        SegmentTree segTree(points.size());

        for (const auto& interval : intervals) {
            int start = compress[interval[0]];
            int end = compress[interval[1]];
            int len = interval[1] - interval[0] + 1;
            segTree.update(start, end, len);
        }

        vector ans;
        for (int q : queries) {
            int idx = compress[q];
            int res = segTree.query(idx);
            ans.push_back(res == INT_MAX ? -1 : res);
        }

        return ans;
    }
};

Java

class SegmentTree:
    def __init__(self, N):
        self.n = N
        self.tree = [float('inf')] * (4 * N)
        self.lazy = [float('inf')] * (4 * N)

    def propagate(self, treeidx, lo, hi):
        if self.lazy[treeidx] != float('inf'):
            self.tree[treeidx] = min(self.tree[treeidx], self.lazy[treeidx])
            if lo != hi:
                self.lazy[2 * treeidx + 1] = min(self.lazy[2 * treeidx + 1], self.lazy[treeidx])
                self.lazy[2 * treeidx + 2] = min(self.lazy[2 * treeidx + 2], self.lazy[treeidx])
            self.lazy[treeidx] = float('inf')

    def update(self, treeidx, lo, hi, left, right, val):
        self.propagate(treeidx, lo, hi)
        if lo > right or hi < left:
            return
        if lo >= left and hi <= right:
            self.lazy[treeidx] = min(self.lazy[treeidx], val)
            self.propagate(treeidx, lo, hi)
            return
        mid = (lo + hi) // 2
        self.update(2 * treeidx + 1, lo, mid, left, right, val)
        self.update(2 * treeidx + 2, mid + 1, hi, left, right, val)
        self.tree[treeidx] = min(self.tree[2 * treeidx + 1], self.tree[2 * treeidx + 2])

    def query(self, treeidx, lo, hi, idx):
        self.propagate(treeidx, lo, hi)
        if lo == hi:
            return self.tree[treeidx]
        mid = (lo + hi) // 2
        if idx <= mid:
            return self.query(2 * treeidx + 1, lo, mid, idx)
        else:
            return self.query(2 * treeidx + 2, mid + 1, hi, idx)

    def update_range(self, left, right, val):
        self.update(0, 0, self.n - 1, left, right, val)

    def query_point(self, idx):
        return self.query(0, 0, self.n - 1, idx)

class Solution:
    def minInterval(self, intervals: List[List[int]], queries: List[int]) -> List[int]:
        points = []
        for interval in intervals:
            points.append(interval[0])
            points.append(interval[1])
        for q in queries:
            points.append(q)

        # Compress the coordinates
        points = sorted(set(points))
        compress = {points[i]: i for i in range(len(points))}

        # Lazy Segment Tree
        segTree = SegmentTree(len(points))

        for interval in intervals:
            start = compress[interval[0]]
            end = compress[interval[1]]
            length = interval[1] - interval[0] + 1
            segTree.update_range(start, end, length)

        ans = []
        for q in queries:
            idx = compress[q]
            
            # query for minSize
            res = segTree.query_point(idx)
            ans.append(res if res != float('inf') else -1)
        return ans

Python

class SegmentTree:
    def __init__(self, N):
        self.n = N
        self.tree = [float('inf')] * (4 * N)
        self.lazy = [float('inf')] * (4 * N)

    def propagate(self, treeidx, lo, hi):
        if self.lazy[treeidx] != float('inf'):
            self.tree[treeidx] = min(self.tree[treeidx], self.lazy[treeidx])
            if lo != hi:
                self.lazy[2 * treeidx + 1] = min(self.lazy[2 * treeidx + 1], self.lazy[treeidx])
                self.lazy[2 * treeidx + 2] = min(self.lazy[2 * treeidx + 2], self.lazy[treeidx])
            self.lazy[treeidx] = float('inf')

    def update(self, treeidx, lo, hi, left, right, val):
        self.propagate(treeidx, lo, hi)
        if lo > right or hi < left:
            return
        if lo >= left and hi <= right:
            self.lazy[treeidx] = min(self.lazy[treeidx], val)
            self.propagate(treeidx, lo, hi)
            return
        mid = (lo + hi) // 2
        self.update(2 * treeidx + 1, lo, mid, left, right, val)
        self.update(2 * treeidx + 2, mid + 1, hi, left, right, val)
        self.tree[treeidx] = min(self.tree[2 * treeidx + 1], self.tree[2 * treeidx + 2])

    def query(self, treeidx, lo, hi, idx):
        self.propagate(treeidx, lo, hi)
        if lo == hi:
            return self.tree[treeidx]
        mid = (lo + hi) // 2
        if idx <= mid:
            return self.query(2 * treeidx + 1, lo, mid, idx)
        else:
            return self.query(2 * treeidx + 2, mid + 1, hi, idx)

    def update_range(self, left, right, val):
        self.update(0, 0, self.n - 1, left, right, val)

    def query_point(self, idx):
        return self.query(0, 0, self.n - 1, idx)

class Solution:
    def minInterval(self, intervals: List[List[int]], queries: List[int]) -> List[int]:
        points = []
        for interval in intervals:
            points.append(interval[0])
            points.append(interval[1])
        for q in queries:
            points.append(q)

        # Compress the coordinates
        points = sorted(set(points))
        compress = {points[i]: i for i in range(len(points))}

        # Lazy Segment Tree
        segTree = SegmentTree(len(points))

        for interval in intervals:
            start = compress[interval[0]]
            end = compress[interval[1]]
            length = interval[1] - interval[0] + 1
            segTree.update_range(start, end, length)

        ans = []
        for q in queries:
            idx = compress[q]
            
            # query for minSize
            res = segTree.query_point(idx)
            ans.append(res if res != float('inf') else -1)
        return ans

JavaScript

class SegmentTree {
    constructor(N) {
        this.n = N;
        this.tree = new Array(4 * N).fill(Infinity);
        this.lazy = new Array(4 * N).fill(Infinity);
    }

    /**
     * @param {number} treeidx
     * @param {number} lo
     * @param {number} hi
     * @return {void}
     */
    propagate(treeidx, lo, hi) {
        if (this.lazy[treeidx] !== Infinity) {
            this.tree[treeidx] = Math.min(this.tree[treeidx], this.lazy[treeidx]);
            if (lo !== hi) {
                this.lazy[2 * treeidx + 1] = Math.min(this.lazy[2 * treeidx + 1], this.lazy[treeidx]);
                this.lazy[2 * treeidx + 2] = Math.min(this.lazy[2 * treeidx + 2], this.lazy[treeidx]);
            }
            this.lazy[treeidx] = Infinity;
        }
    }

    /**
     * @param {number} treeidx
     * @param {number} lo
     * @param {number} hi
     * @param {number} left
     * @param {number} right
     * @param {number} val
     * @return {void}
     */
    update(treeidx, lo, hi, left, right, val) {
        this.propagate(treeidx, lo, hi);
        if (lo > right || hi < left) return;
        if (lo >= left && hi <= right) {
            this.lazy[treeidx] = Math.min(this.lazy[treeidx], val);
            this.propagate(treeidx, lo, hi);
            return;
        }
        const mid = Math.floor((lo + hi) / 2);
        this.update(2 * treeidx + 1, lo, mid, left, right, val);
        this.update(2 * treeidx + 2, mid + 1, hi, left, right, val);
        this.tree[treeidx] = Math.min(this.tree[2 * treeidx + 1], this.tree[2 * treeidx + 2]);
    }

    /**
     * @param {number} treeidx
     * @param {number} lo
     * @param {number} hi
     * @param {number} idx
     * @return {number}
     */
    query(treeidx, lo, hi, idx) {
        this.propagate(treeidx, lo, hi);
        if (lo === hi) return this.tree[treeidx];
        const mid = Math.floor((lo + hi) / 2);
        if (idx <= mid) return this.query(2 * treeidx + 1, lo, mid, idx);
        else return this.query(2 * treeidx + 2, mid + 1, hi, idx);
    }

    /**
     * @param {number} left
     * @param {number} right
     * @param {number} val
     * @return {number}
     */
    updateRange(left, right, val) {
        this.update(0, 0, this.n - 1, left, right, val);
    }

    /**
     * @param {number} idx
     * @return {number}
     */
    queryPoint(idx) {
        return this.query(0, 0, this.n - 1, idx);
    }
}

class Solution {
    /**
     * @param {number[][]} intervals
     * @param {number[]} queries
     * @return {number[]}
     */
    minInterval(intervals, queries) {
        const points = [];
        for (const interval of intervals) {
            points.push(interval[0]);
            points.push(interval[1]);
        }
        for (const q of queries) {
            points.push(q);
        }
        const uniquePoints = [...new Set(points)].sort((a, b) => a - b);
        const compress = new Map();
        uniquePoints.forEach((point, idx) => {
            compress.set(point, idx);
        });
        const segTree = new SegmentTree(uniquePoints.length);
        for (const interval of intervals) {
            const start = compress.get(interval[0]);
            const end = compress.get(interval[1]);
            const length = interval[1] - interval[0] + 1;
            segTree.updateRange(start, end, length);
        }
        const ans = [];
        for (const q of queries) {
            const idx = compress.get(q);
            const res = segTree.queryPoint(idx);
            ans.push(res === Infinity ? -1 : res);
        }
        return ans;
    }
}

Unlock this article for Free,
by logging in

Minimum Interval to Include Each Query

Finding the Minimum Interval to Include Each Query

Problem Description

Your Task:

Key Notes:

Key Idea:

Algorithm

There are mainly Four approach to solve this problem –

1. Brute Force

2. Sweep Line Algorithm

Time & Space Complexity

3. Min Heap

4. Min Segment Tree (Lazy Propagation)

More Articles

30+ Companies are Hiring

Unlock this article for Free, by logging in

Minimum Interval to Include Each Query

Finding the Minimum Interval to Include Each Query

Problem Description

Your Task:

Key Notes:

Key Idea:

Algorithm

There are mainly Four approach to solve this problem –

1. Brute Force

2. Sweep Line Algorithm

Time & Space Complexity

3. Min Heap

4. Min Segment Tree (Lazy Propagation)

More Articles

30+ Companies are Hiring

Unlock this article for Free,
by logging in