✏️
leetcode solution
  • Leetcode Solutions
  • LeetCode 1. Two Sum
  • LeetCode 2. Add Two Numbers
  • LeetCode 3. Longest Substring Without Repeating Characters
  • LeetCode 4. Median of Two Sorted Arrays
  • LeetCode 5. Longest Palindromic Substring
  • LeetCode 6. ZigZag Conversion
  • LeetCode 7. Reverse Integer
  • LeetCode 8. String to Integer (atoi)
  • LeetCode 9. Palindrome Number
  • LeetCode 10. Regular Expression Matching
  • LeetCode 11. Container With Most Water
  • LeetCode 12. Integer to Roman
  • LeetCode 13. Roman to Integer
  • LeetCode 14. Longest Common Prefix
  • LeetCode 15. 3Sum
  • LeetCode 16. 3Sum Closest
  • LeetCode 17. Letter Combinations of a Phone Number
  • LeetCode 18. 4Sum
  • LeetCode 19. Remove Nth Node From End of List
  • LeetCode 20. Valid Parentheses
  • LeetCode 21. Merge Two Sorted Lists
  • LeetCode 22. Generate Parentheses
  • LeetCode 23. Merge k Sorted Lists
  • LeetCode 24. Swap Nodes in Pairs
  • LeetCode 25. Reverse Nodes in k-Group
  • LeetCode 26. Remove Duplicates from Sorted Array
  • LeetCode 27. Remove Element
  • LeetCode 28. Implement strStr()
  • LeetCode 29. Divide Two Integers
  • LeetCode 30. Substring with Concatenation of All Words
  • LeetCode 31. Next Permutation
  • LeetCode 32. Longest Valid Parentheses
  • LeetCode 33. Search in Rotated Sorted Array
  • LeetCode 42. Trapping Rain Water
  • LeetCode 56. Merge Intervals
  • LeetCode 67. Add Binary
  • LeetCode 81. Search in Rotated Sorted Array II
  • LeetCode 124. Binary Tree Maximum Path Sum
  • LeetCode 125. Valid Palindrome
  • LeetCode 153. Find Minimum in Rotated Sorted Array
  • LeetCode 154. Find Minimum in Rotated Sorted Array II
  • LeetCode 157. Read N Characters Given Read4
  • LeetCode 158. Read N Characters Given Read4 II - Call multiple times
  • LeetCode 236. Lowest Common Ancestor of a Binary Tree
  • LeetCode 238. Product of Array Except Self
  • LeetCode 269. Alien Dictionary
  • Leetcode 295. Find Median from Data Stream
  • Leetcode 297. Serialize and Deserialize Binary Tree
  • LeetCode 300. Longest Increasing Subsequence
  • LeetCode 301. Remove Invalid Parentheses
  • LeetCode 336. Palindrome Pairs
  • LeetCode 407. Trapping Rain Water II
  • LeetCode 415. Add Strings
  • LeetCode 426. Convert Binary Search Tree to Sorted Doubly Linked List
  • LeetCode 489. Robot Room Cleaner
  • LeetCode 560. Subarray Sum Equals K
  • LeetCode 680. Valid Palindrome II
  • LeetCode 710. Random Pick with Blacklist
  • LeetCode 721. Accounts Merge
  • LeetCode 863. All Nodes Distance K in Binary Tree
  • LeetCode 918. Maximum Sum Circular Subarray
  • LeetCode 953. Verifying an Alien Dictionary
  • LeetCode 973. K Closest Points to Origin
  • LeetCode 1249. Minimum Remove to Make Valid Parentheses
  • LeetCode 1428. Leftmost Column with at Least a One
  • LeetCode 1570. Dot Product of Two Sparse Vectors
  • LeetCode 1644. Lowest Common Ancestor of a Binary Tree II
  • LeetCode 1650. Lowest Common Ancestor of a Binary Tree III
  • LeetCode 1676. Lowest Common Ancestor of a Binary Tree IV
  • Leetcode 1727. Largest Submatrix With Rearrangements
  • LeetCode 1751. Maximum Number of Events That Can Be Attended II
  • LeetCode 1754. Largest Merge Of Two Strings
  • LeetCode 1755. Closest Subsequence Sum
  • LeetCode 1760. Minimum Limit of Balls in a Bag
  • LeetCode 1761. Minimum Degree of a Connected Trio in a Graph
  • LeetCode 1764. Form Array by Concatenating Subarrays of Another Array
  • LeetCode 1765. Map of Highest Peak
  • LeetCode 1766. Tree of Coprimes
  • LeetCode 1770. Maximum Score from Performing Multiplication Operations
  • LeetCode 1771. Maximize Palindrome Length From Subsequences
  • LeetCode 1774. Closest Dessert Cost
  • LeetCode. 1775 Equal Sum Arrays With Minimum Number of Operations
  • LeetCode 1776. Car Fleet II
  • LeetCode 1778. Shortest Path in a Hidden Grid
  • LeetCode 1779. Find Nearest Point That Has the Same X or Y Coordinate
  • LeetCode 1780. Check if Number is a Sum of Powers of Three
  • LeetCode 1781. Sum of Beauty of All Substrings
  • LeetCode 1782. Count Pairs Of Nodes
  • LeetCode 1784. Check if Binary String Has at Most One Segment of Ones
  • LeetCode 1785. Minimum Elements to Add to Form a Given Sum
  • LeetCode 1786. Number of Restricted Paths From First to Last Node
  • LeetCode 1787. Make the XOR of All Segments Equal to Zero
  • LeetCode 1788. Maximize the Beauty of the Garden
  • LeetCode 1790. Check if One String Swap Can Make Strings Equal
  • LeetCode 1791. Find Center of Star Graph
  • LeetCode 1792. Maximum Average Pass Ratio
  • LeetCode 1793. Maximum Score of a Good Subarray
  • LeetCode 1794. Count Pairs of Equal Substrings With Minimum Difference
  • LeetCode 1796. Second Largest Digit in a String
  • LeetCode 1797. Design Authentication Manager
  • LeetCode 1798. Maximum Number of Consecutive Values You Can Make
  • LeetCode 1799. Maximize Score After N Operations
  • LeetCode 1800. Maximum Ascending Subarray Sum
  • LeetCode 1801. Number of Orders in the Backlog
  • LeetCode 1802. Maximum Value at a Given Index in a Bounded Array
  • LeetCode 1803. Count Pairs With XOR in a Range
  • LeetCode 1804. Implement Trie II (Prefix Tree)
  • LeetCode 1805. Number of Different Integers in a String
  • LeetCode 1807. Evaluate the Bracket Pairs of a String
  • LeetCode 1808. Maximize Number of Nice Divisors
  • LeetCode 1810. Minimum Path Cost in a Hidden Grid
  • LeetCode 1812. Determine Color of a Chessboard Square
  • LeetCode 1813. Sentence Similarity III
  • LeetCode 1814. Count Nice Pairs in an Array
  • LeetCode 1815. Maximum Number of Groups Getting Fresh Donuts
  • LeetCode 1816. Truncate Sentence
  • LeetCode 1817. Finding the Users Active Minutes
  • LeetCode 1818. Minimum Absolute Sum Difference
  • LeetCode 1819. Number of Different Subsequences GCDs
  • LeetCode 1820. Maximum Number of Accepted Invitations
  • LeetCode 1822. Sign of the Product of an Array
  • LeetCode 1824. Minimum Sideway Jumps
  • LeetCode 1825. Finding MK Average
  • LeetCode 1826. Faulty Sensor
  • LeetCode 1827. Minimum Operations to Make the Array Increasing
  • LeetCode 1828. Queries on Number of Points Inside a Circle
  • LeetCode 1829. Maximum XOR for Each Query
  • LeetCode 1830. Minimum Number of Operations to Make String Sorted
  • LeetCode 1832. Check if the Sentence Is Pangram
  • LeetCode 1833. Maximum Ice Cream Bars
  • LeetCode 1834. Single-Threaded CPU
  • LeetCode 1835. Find XOR Sum of All Pairs Bitwise AND
  • LeetCode 1836. Remove Duplicates From an Unsorted Linked List
  • LeetCode 1837. Sum of Digits in Base K
  • LeetCode 1839. Longest Substring Of All Vowels in Order
  • LeetCode 1840. Maximum Building Height
  • LeetCode 1847. Closest Room
  • LeetCode 1850. Minimum Adjacent Swaps to Reach the Kth Smallest Number
  • LeetCode 1851. Minimum Interval to Include Each Query
Powered by GitBook
On this page

Was this helpful?

LeetCode 1851. Minimum Interval to Include Each Query

You are given a 2D integer array intervals, where intervals[i] = [lefti, righti] describes the ith interval starting at lefti and ending at righti (inclusive). The size of an interval is defined as the number of integers it contains, or more formally righti - lefti + 1.

You are also given an integer array queries. The answer to the jth query is the size of the smallest interval i such that lefti <= queries[j] <= righti. If no such interval exists, the answer is -1.

Return an array containing the answers to the queries.

Example 1:

Input: intervals = [[1,4],[2,4],[3,6],[4,4]], queries = [2,3,4,5]
Output: [3,3,1,4]
Explanation: The queries are processed as follows:
- Query = 2: The interval [2,4] is the smallest interval containing 2. The answer is 4 - 2 + 1 = 3.
- Query = 3: The interval [2,4] is the smallest interval containing 3. The answer is 4 - 2 + 1 = 3.
- Query = 4: The interval [4,4] is the smallest interval containing 4. The answer is 4 - 4 + 1 = 1.
- Query = 5: The interval [3,6] is the smallest interval containing 5. The answer is 6 - 3 + 1 = 4.

Example 2:

Input: intervals = [[2,3],[2,5],[1,8],[20,25]], queries = [2,19,5,22]
Output: [2,-1,4,6]
Explanation: The queries are processed as follows:
- Query = 2: The interval [2,3] is the smallest interval containing 2. The answer is 3 - 2 + 1 = 2.
- Query = 19: None of the intervals contain 19. The answer is -1.
- Query = 5: The interval [2,5] is the smallest interval containing 5. The answer is 5 - 2 + 1 = 4.
- Query = 22: The interval [20,25] is the smallest interval containing 22. The answer is 25 - 20 + 1 = 6.

Constraints:

  • 1 <= intervals.length <= 10^5

  • 1 <= queries.length <= 10^5

  • queries[i].length == 2

  • 1 <= lefti <= righti <= 10^7

  • 1 <= queries[j] <= 10^7

Solution

class Solution {
public:
    vector<int> minInterval(vector<vector<int>>& intervals, vector<int>& queries) {
        int m = queries.size();

        sort(intervals.begin(), intervals.end(),[](const vector<int>& lhs, const vector<int>& rhs){
            return lhs[1] - lhs[0] < rhs[1] - rhs[0];
        });
        
        set<pair<int, int>> myset;
        for (int i = 0; i < m; i++) {
            myset.insert({queries[i], i});
        }
        
        vector<int> ans(m, -1);
        for (const vector<int>& interval : intervals) {
            auto it = myset.lower_bound({interval[0], 0});
            
            while (it != myset.end() && it->first <= interval[1]) {
                ans[it->second] = interval[1] - interval[0] + 1;
                it = myset.erase(it);
            }
        }
        
        return ans;
    }
};
PreviousLeetCode 1850. Minimum Adjacent Swaps to Reach the Kth Smallest Number

Last updated 4 years ago

Was this helpful?

English Version in Youtube
中文版解答Youtube Link
中文版解答Bilibili Link