**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 :

` ````
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

## Pair Sums

Given an array, we define its value to be the value obtained by following these instructions: Write down all pairs of numbers from this array. Compute the product of each pair. Find the sum of all the products. For example, for a given array, for a given array [7,2 ,-1 ,2 ] Note that ( 7 , 2 ) is listed twice, one for each occurrence of 2. Given an array of integers, find the largest v

View Solution →## Lazy White Falcon

White Falcon just solved the data structure problem below using heavy-light decomposition. Can you help her find a new solution that doesn't require implementing any fancy techniques? There are 2 types of query operations that can be performed on a tree: 1 u x: Assign x as the value of node u. 2 u v: Print the sum of the node values in the unique path from node u to node v. Given a tree wi

View Solution →## Ticket to Ride

Simon received the board game Ticket to Ride as a birthday present. After playing it with his friends, he decides to come up with a strategy for the game. There are n cities on the map and n - 1 road plans. Each road plan consists of the following: Two cities which can be directly connected by a road. The length of the proposed road. The entire road plan is designed in such a way that if o

View Solution →## Heavy Light White Falcon

Our lazy white falcon finally decided to learn heavy-light decomposition. Her teacher gave an assignment for her to practice this new technique. Please help her by solving this problem. You are given a tree with N nodes and each node's value is initially 0. The problem asks you to operate the following two types of queries: "1 u x" assign x to the value of the node . "2 u v" print the maxim

View Solution →## Number Game on a Tree

Andy and Lily love playing games with numbers and trees. Today they have a tree consisting of n nodes and n -1 edges. Each edge i has an integer weight, wi. Before the game starts, Andy chooses an unordered pair of distinct nodes, ( u , v ), and uses all the edge weights present on the unique path from node u to node v to construct a list of numbers. For example, in the diagram below, Andy

View Solution →## Heavy Light 2 White Falcon

White Falcon was amazed by what she can do with heavy-light decomposition on trees. As a resut, she wants to improve her expertise on heavy-light decomposition. Her teacher gave her an another assignment which requires path updates. As always, White Falcon needs your help with the assignment. You are given a tree with N nodes and each node's value Vi is initially 0. Let's denote the path fr

View Solution →