Count Contained Intervals - Amazon Top Interview Questions


Problem Statement :


You are given a two-dimensional list of integers intervals. Each value is unique and contains an inclusive interval [start, end]. Return the number of intervals are contained by another interval. An interval that's contained by multiple other intervals should only be counted once.

An interval [s0, e0] contains another interval [s1, e1] if s0 ≤ s1 and e0 ≥ e1.

Constraints

0 ≤ n ≤ 100,000 where n is the length of intervals

Example 1

Input

intervals = [
    [1, 5],
    [2, 3],
    [3, 6],
    [4, 4]
]

Output

2

Explanation


[2, 3] and [4, 4] are contained by [1, 5]. [4, 4] is also contained by [3, 6] but we don't count it again.


Example 2

Input

intervals = [
    [1, 2],
    [2, 3],
    [1, 5]
]

Output

2

Explanation

Both [1, 2] and [2, 3] are contained by [1, 5]


Solution :



title-img 




                        Solution in C++ :

int solve(vector<vector<int>>& nums) {
    sort(nums.begin(), nums.end(), [](vector<int>& a, vector<int>& b) {
        if (a[0] == b[0]) return a[1] > b[1];
        return a[0] < b[0];
    });
    int count = 0, pe = INT_MIN;
    for (auto& n : nums) {
        if (n[1] <= pe) {
            count += 1;
        } else {
            pe = n[1];
        }
    }
    return count;
}
                    




                        Solution in Python : 
                            
class Solution:
    def solve(self, intervals):
        events = []
        OPEN, CLOSE = 0, 1

        for i, (start, end) in enumerate(intervals):
            events.append((start, OPEN, end, i))
            events.append((end, CLOSE, end, i))

        events.sort(key=lambda x: (x[0], -x[2]))

        ans = 0
        balance = 0
        max_end = float("-inf")

        for time, event_type, end, idx in events:
            if event_type == OPEN and end <= max_end:
                ans += 1

            if event_type == OPEN:
                max_end = max(max_end, end)

        return ans


View More Similar Problems

Tree: Preorder Traversal

Complete the preorder function in the editor below, which has 1 parameter: a pointer to the root of a binary tree. It must print the values in the tree's preorder traversal as a single line of space-separated values. Input Format Our test code passes the root node of a binary tree to the preOrder function. Constraints 1 <= Nodes in the tree <= 500 Output Format Print the tree's

View Solution →

Tree: Postorder Traversal

Complete the postorder function in the editor below. It received 1 parameter: a pointer to the root of a binary tree. It must print the values in the tree's postorder traversal as a single line of space-separated values. Input Format Our test code passes the root node of a binary tree to the postorder function. Constraints 1 <= Nodes in the tree <= 500 Output Format Print the

View Solution →

Tree: Inorder Traversal

In this challenge, you are required to implement inorder traversal of a tree. Complete the inorder function in your editor below, which has 1 parameter: a pointer to the root of a binary tree. It must print the values in the tree's inorder traversal as a single line of space-separated values. Input Format Our hidden tester code passes the root node of a binary tree to your $inOrder* func

View Solution →

Tree: Height of a Binary Tree

The height of a binary tree is the number of edges between the tree's root and its furthest leaf. For example, the following binary tree is of height : image Function Description Complete the getHeight or height function in the editor. It must return the height of a binary tree as an integer. getHeight or height has the following parameter(s): root: a reference to the root of a binary

View Solution →

Tree : Top View

Given a pointer to the root of a binary tree, print the top view of the binary tree. The tree as seen from the top the nodes, is called the top view of the tree. For example : 1 \ 2 \ 5 / \ 3 6 \ 4 Top View : 1 -> 2 -> 5 -> 6 Complete the function topView and print the resulting values on a single line separated by space.

View Solution →

Tree: Level Order Traversal

Given a pointer to the root of a binary tree, you need to print the level order traversal of this tree. In level-order traversal, nodes are visited level by level from left to right. Complete the function levelOrder and print the values in a single line separated by a space. For example: 1 \ 2 \ 5 / \ 3 6 \ 4 F

View Solution →